Eulerian Path: Drawing Without Lifting or Retracing

Drawing without lifting a pen and retracing any edge [Presentation] [Transcrtipt]

Consider the two shapes shown in . Do you think you can draw them subject to following two rules:

Don't lift your pen.
Don't trace any edge more than once.

shapes to demonstrate eulerian path — Shapes to demonstrate the concept of Eulerian path

If you haven’t seen this puzzle before, now’s a good time to try it yourself.

Assuming you gave it a try, most of you probably figured out how to draw the first shape. If not, don’t worry — I’ll demonstrate it in a moment. Now, for the second shape — you likely found it tricky. That’s because it’s impossible to draw the second shape without lifting your pen or retracing a line.

A natural question comes up about the possibility/impossibility of drawing without lifting your pen and retracing any edge more than once.

When is it possible—or impossible—to draw a shape without lifting your pen and retracing any edge?

To answer this question, we’ll look at the two example shapes () in detail. But before we dive into the puzzle, let’s define a key idea: Eulerian path. If it’s possible to trace a shape following these rules — no lifting, no repeating edges — that path is called an Eulerian path. This idea comes from graph theory in mathematics. There's a theoretical result guaranteeing existence of an Eulerian path under certain conditions. Instead of deriving those conditions, we will use the two shapes in to understand those conditions qualitatively. We summarize the conditions guaranteeing existence of an Eulerian path in without a proof.

Proof of possibility and impossibility of existence of Eulerian path

Possibility of an Eulerian path for the first shape

Let’s start with the first shape.

shape with a possible eulerian path — Shape with a possible Eulerian path

We claim that this shapes has an Eulerian path and the simplest way to prove it is by drawing it.

One possible Eulerian path for the first shape is shown in . Start at vertex B, then go to A, D, back to B, then C, D, E, A, and finally end at C. Note that each edge is used exactly once making it a valid Eulerian path. This proves existence of an Eulerian path for the first shape.

Impossibility of Eulerian path for the second shape

The second shape looks similar to the first shape but lacks an important feature essential for existence of an Eulerian path.

shape with impossible eulerian path — Shape with impossible Eulerian path

To understand why it is impossible to draw an Eulerian path for the second shape, let’s consider two cases. In case 1, we consider drawing an Eulerian path starting and ending at the same vertex. In case 2, we consider drawing an Eulerian path starting and ending at the different vertices.

If case 1 is possible, Eulerian path is also known as an Eulerian circuit — it’s a special kind of Eulerian path where you return to the starting point. In this case, every vertex must have an even number of edges connected to it. That’s because each time you draw an edge to reach vertex, you must draw another edge to leave the vertex. So, edges come in pairs — meaning each vertex must have an even degree (an even number of connected edges). If even one vertex has an odd number of edges, it breaks the condition — and you can't return to the starting point without repeating or lifting the pen.

If case 2 is possible, Eulerian path begins at one vertex and ends at another. In this case exactly two vertices can have an odd number of edges — the start and end points. All other vertices must have an even number of edges. Why? Because the start vertex has one extra edge going out, and the end vertex has one extra edge coming in. All other vertices must still follow the in-out pairing — so they need even degrees.

Now, look at the second shape closely. It has four vertices, and all four have an odd number of edges connected to them. That means it doesn’t fit either case — so it’s not possible to draw an Eulerian path for the second shape.

Conclusion

To summarize, a connected graph has an Eulerian path if it satisfies one of these two cases.

All vertices have an even number of edges connected to it. In this case an Eulerian path starts and ends at the same vertex.
Only 2 vertices have an odd of edges connected to it. In this case, an Eulerian path starts and ends at different vertices.

Remarks

In our analysis, we have shown neccessity of these two conditions for existence of an Eulerian path. To prove sufficiency, one would have to provide an algorithm to generate an Eulerian path for any given shape satisfying any of these two conditions.

Author

Anurag Gupta is an M.S. graduate in Electrical and Computer Engineering from Cornell University. He also holds an M.Tech degree in Systems and Control Engineering and a B.Tech degree in Electrical Engineering from the Indian Institute of Technology, Bombay.

Comment

Past Comments

No comments yet. Be the first!