Tracing a Figure Without Lifting Your Pencil

Date: 03/09/2001 at 19:57:01
From: Kerri
Subject: Tracing a figure without lifting your pencil

My students have asked me about whether it is possible to trace a 
certain figure without retracing or lifting the pencil. I have not 
studied discrete math in a while, and can't remember how to tell if it 
can be done. We have tried to do it several times with no luck. The 
figure is a square with both diagonals drawn in, and half circles on 
all four sides of the square.

Date: 03/09/2001 at 20:13:14
From: Doctor Schwa
Subject: Re: Tracing a figure without lifting your pencil

Hi Kerri,

This problem was first solved by Euler, and in fact searching the 
Dr. Math archives at:

   http://mathforum.org/mathgrepform.html   

for the words "Euler path" found a few useful links on this topic.

The way Euler figured out this type of problem is really clever, 
though, and I can't resist telling you a bit about it myself.

As you walk around on your figure, at each "intersection" you have to 
come in along one path and leave on another. That is, you use up two 
of the paths that meet at that intersection each time you visit it.

Thus, to have a complete traversal possible, every intersection has to 
have an even number of paths meeting at it.

Oh, wait - at the place where you start, you use up only one path when 
you leave. And the same is true of the place where you end.

So, if you end up where you started, you have to use up an even number 
of paths at every intersection, but if you start and end at different 
places, those two intersections will have to have an odd number of 
paths meeting there, and all the rest of the intersections still have 
to be even.

In graph theory, people call the intersections "vertices," the paths 
"edges," and the number of paths meeting at an intersection the 
"degree of the vertex," but they still use the same logic.

I hope you can give your students some hints and let them have the joy 
of discovering this idea for themselves!

Have fun.

- Doctor Schwa, The Math Forum
  http://mathforum.org/dr.math/