Solving tracing problems using graph theory

A couple of weeks ago, I was looking at a standardized test and came across the following “tracing” problem:

Which of the drawings below can you completely trace without lifting your pencil or retracing a previously traced part? 

01_pencilliftprobs_original

When I was a teenager, I had seen similar questions to this one, but was always frustrated that I couldn’t figure out a way to solve them except by trial and error. Twenty years later, thanks to being exposed to different areas of mathematics as a tutor, I instantly saw a systematic way to answer them. Try solving the test question on your own first before reading my approach below.

Give up?

We can solve this problem by transforming the drawings into graphs. To do this, draw a dot where the lines of a drawing intersect. These are the vertices of your graph. The lines that connect vertices are edges.

02_pencilliftprobs_vertices_letters

Now, we need this man, or, namely, what he discovered:

leonhard_euler
Leonhard Euler (1707-1783)

Euler was able to prove the following:*

On graphs where a path from one vertex can be made to any other, it is possible to traverse all the graph’s edges only once if and only if the path starts and finishes at vertices with an odd number of edges coming from them and all the other vertices have an even number of edges coming from them.

The above is what is known as an Euler path. To see how it works, let’s look at the graphs below. The necessary two vertices with an odd number of edges coming from them have been coloured blue. I have also drawn in (rather badly) red arrows to indicate a path which can be taken to go through all the edges starting at one blue vertex and ending at the other.

02_pencilliftprobs_vertices_paths_png

Thus, here are some Euler paths for graphs A, B and D.

A: abcbcd

B: abcfedacd

D: bedcbace

As you can see, if you were to follow these paths with your pencil, you would never have to lift it nor retrace an edge.

Okay, but what about graphs C and E? Well, a close look at graph E look will show that both blue vertices have an even number of edges protruding from them. So, an Euler path is not possible. No, but an Euler circuit is:

On graphs where a path from one vertex can be made to any other, it is possible to start and end at the same vertex and traverse all the graph’s edges only once if and only if all the graph’s vertices have an even number of edges coming from them.

And this is exactly case with graph E. A possible Euler circuit then is abcdedba. And, since there are four other vertices who are even, there are at least four other possible circuits we can make.

This leaves graph C. Looking at its vertices we notice two things: one, not all the vertices have an even number of edges coming from them, and two, there are more than two vertices with an odd number of edges sticking out: c, d, e, and f. The first observation excludes the possibility of an Euler circuit; the second, an Euler path. Consequently, it’s not possible to go over all the edges of graph C without lifting your pencil or retracing an edge. If you can, please let me know and I’ll heartily eat my shoe!

*Leonhard Euler contributed a lot to mathematics. One of the fun things I have learned about him was that he was able to figure out that 4,294,967,297, which Pierre de Fermat had conjectured was prime, was actually a composite number, i.e. 641*6,700,417. Impressive enough, but even more so since Euler supposedly figured this out in his head. (Stewart, Redlin, Saleem Watson. Algebra and Trigonometry, Third Edition. Brooks/Cole, 2012. p. 92).
† I think there are just four other circuits in this case, but I haven’t checked, so I could be mistaken.
‡ I’m not as honourable as Werner Herzog, so I’ll pass on eating my shoe. I will, however, feel quite embarrassed and guilty about my answer. The mistakes I fear most are those borne from overconfidence, thinking I know what I’m doing when really I don’t.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s