Associated Topics || Dr. Math Home || Search Dr. Math

### 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/

Associated Topics:
High School Discrete Mathematics
High School Puzzles
Middle School Puzzles

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search