“Draw Without Lifting Pencil” Puzzles (Euler Paths & Circuits)

envelope
Shape 1

Remember this shape? I bet you could tell me the answer without me asking the question. Most of us solved this puzzle million times when we were at primary school.

Let me ask the question again: how can you draw this shape without tracing the same line twice and without taking the pencil off the paper?

I will talk about the mathematical approach to this problem in this post, which includes graph theory (so it would be very nice if you go and read the basics of graph theory before continuing, although it is not that necessary since I assume you will understand the general concept).

For this shape, you probably memorized the answer by doing it so many times. You know where to start and where to finish. However, suppose you see a shape like this:

main-qimg-29f049440bad4571da709d94211bcaf3
Shape 2

Now we have to modify our question a little: can you draw this?

We can convert the shape into a graph by assigning vertices to intersections and assigning edges to the lines between the vertices. Let’s try this with our popular shape:

envelope

(There are ten edges in this graph: 1-2, 1-3, 2-3, 2-4, 2-5, 3-4, 3-6, 4-5, 4-6 and 5-6.)

Now we are looking for a path (or a cycle) in the graph that visits every edge exactly once. This problem was solved by the famous mathematician Euler in 1736 and is considered to be the beginning of the graph theory. The problem is often referred as an Euler path or Euler circuit problem. An Euler path starts and ends at different vertices, whereas an Euler circuit starts and ends at the same vertex.

For an Euler path P, for every vertex v other than the endpoints, the path enters v the same number of times it leaves v (what goes in must come out). Then, there should be twice this number of edges having v as an endpoint (try to visualize this: -*-, where asterisk is a vertex which has one entrance = one exit, and to which one times two edges are connected).  Therefore, every v should have an even degree (even number of edges should be connected to v).

Now suppose P starts at vertex p and ends at vertex q. Then P should leave p one more time than it enters, and enter q one more time than it leaves. This makes degrees of p and q even degree minus one, therefore, the endpoints of P should have odd degrees (odd number edges should be connected to v).

Then the conclusion  for P is this:

“If a graph has an Euler path, then it must have exactly two odd vertices.”

For an Euler circuit C, the starting point must be the same with the endpoint, so C enters the endpoint the same number of times it leaves it, which makes it a vertex of even degree.

Then the conclusion for C is this:

“If a graph has an Euler circuit, then all of its vertices must be even vertices.”

Let’s apply these on our examples. In shape 1, vertices 1, 2, 3 and 4 all have even degrees of two, four, four and four, respectively. Vertices 5 and 6 both have odd degrees of three. Then, this graph has at least one Euler path but it does not have any Euler circuit. In shape 2, there are four vertices of odd degree and one vertex of even degree, so it does not have any Euler path or Euler circuit.

Question: Is it possible for a graph to have both an Euler path and an Euler circuit? 
Answer: No. (I think you can figure this out by yourself. I trust you!)

Now we have to focus on our main question: if a path/circuit exists, how do we find it?

For small graphs, you could try every possibility, of course, but in real life applications there will surely be graphs with thousands or millions of vertices and trial-and-error method will take so much time even with a computer program.

A systematic approach would be Fleury’s Algorithm. In this algorithm, our motto is this old proverb: Don’t burn your bridges behind you (it also exists in Turkish: Gectigin kopruleri yakma. I like the English version better though). In graph theory, bridge is the only edge which connects two separate sections of the graph. Removing this edge from the graph would make it disconnected.

Bridges_800

To find an Euler path/circuit in a graph:

  • Make sure it has one.
  •  If you are looking for an Euler path, start from any odd vertex. Else, start from any vertex.
  • A non-bridge ALWAYS has priority over a bridge. ALWAYS CHOOSE THE NON-BRIDGE.
  • Delete the edge that you have traversed.
  • If you do not have any edges left, stop.

Let’s see an example (I am always taking the images from the other sites in this post but I will start with a different vertex, I promise).

bridge.png

In this graph, vertices A, B, C, D, E and F are all even, so we will find an Euler circuit. We could start with any vertex, say B. (1) Then we would proceed again with any one of them, say A. From A, there is no bridge so we can safely (2) travel to D. Then from D, we would either (3) travel to F or C (say C) BUT DEFINITELY NOT B since we would get stuck at B, we would burn the bridge (…ne gemiler yaktim). Then we could proceed with (4) A or E (say A) (not F!), then with (5) E, then (6) C, (7) F, (8) D, (9) B, and since there is no edge left we would finally stop.

(Notice that we started and ended with vertex B, as we were supposed to do.)

If we go back to shape 1, it does not matter if you start from 5 or 6 since the solutions are mirror images of each other. There are 44 possible solutions if you start from vertex 5 and there are only 10 ways to lose.

HausVomNikolaus.svg.png
Ways to win this game (Do not forget to say das ist das Haus vom Ni-ko-laus while trying these at home!)

Since there are so many solutions to this, let’s see an example of a failure. If we follow the path 6-5-4-3-6-4-2 and delete all the edges that we travel, the final graph would look like this:

envelope

If we continue with vertex 5, which is a bridge, we would get stuck there, so we would have to lift our pencil to draw this shape.

I hope you are not bored yet. If you are, though, here is a small exercise for you. The question is this: can you draw the shape below without tracing the same line twice and without taking the pencil off the paper?

path

I hear you say “No, since it neither contains zero nor two odd vertices.”

Well, the answer is…

YES!!!! You could draw it!

“WHAT?! But how? I trusted you, Ezgi!”

Here’s how:

(Well, he did lift his hand… So Euler and I are not liars after all…)

Source:

  1. math.ku.edu
  2. ncsu.edu
  3. Haus vom Nikolaus
  4. Data Structures and Algorithm Analysis in C++, Mark A. Weiss, Fourth Edition

 

 

Advertisements

2 thoughts on ““Draw Without Lifting Pencil” Puzzles (Euler Paths & Circuits)

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