Need a hint?

It is impossible to draw the following design without lifting your pencil from the page, traversing each and every edge precisely once.

Suppose now, however, you are permitted to trace over a small number of edges twice in order to complete the picture. What is the minimal number of edges that must be reused to draw the figure?

Scroll down for the solution to the original problem.

Click here for the solution to the Challenge Problem

One can see by trial and error that design D can be traced without lifting one’s pencil from the page and without retracing the same line more than once. Given that multiple choice questions are usually designed to have just one correct solution, identifying figure D as “traceable” is all one needs to do correctly answer the question. But it would be nice to have a mathematical explanation as to why designs A, B, and C cannot be properly traced. For ease of language, let’s regard each design as a street map. We’ll call each line in the design a “street” and each location where two or more streets meet an “intersection.” (Mathematicians like to use the words “edge” and “vertex,” respectively, for these.) If one were able to trace a given street map with a pencil, traversing each street precisely once, what can be said about the number of streets that meet at each intersection? To answer this, note that one is likely to visit the same point of intersection multiple times as one traces the design. Notice too that each time one visits a given intersection along one street, one must exit along a different street. Thus the streets at a particular intersection can be grouped into “enter-exit” pairs, showing that the number of streets emanating from any particular intersection must be even. There are two exceptions to this, however. If one starts at a particular intersection, then one begins the journey exiting along a street that is not matched with a previous “entering” street (but all the remaining streets emanating from this intersection come in enter-exit pairs). Similarly, if one ends the journey at an alternative intersection, then the final “entering” street remains unmatched with an “exiting” street. (If one begins and ends the journey at the same intersection, however, then the initial “exit” street is matched with the final “enter” street and all streets at this intersection are again paired.) In summary:

If a street map can be traced traversing each and every street precisely once, then either every intersection has an even number of streets emanating from it, or there are precisely two intersections with an odd number of emanating streets. (These two “odd intersections” represent the start and end points of the journey.)

So let’s now check … Does figure A follow this model? Notice that each intersection located at the corner of the square has three emanating streets. There are four “odd intersections” (not two) showing that it is impossible to properly trace this design. Similarly, design B possesses four odd intersections as does design C establishing the impossibility of properly tracing these designs as well. This establishes mathematically that neither A, B, nor C is the solution to the puzzle. For those that would like to think a little more deeply about matters, there is still one remaining issue: Is the converse of the above statement valid? That is, if one is given a street map design that possesses either zero or two “odd” intersections, is it guaranteed that one can indeed trace the design without lifting one’s pencil from the page and without traversing the same street more than once?

If you attempted the Challenge Puzzle, click here for the solution and explanation.