Is it possible to draw this picture without lifting the pen?

Question

Some days ago, our math teacher said that he would give a good grade to the first one that will manage to draw this:

To draw this without lifting the pen and without tracing the same line more than once. It's a bit like the "nine dots" puzzle but here I didn't find any working solution. So I have two questions:

• is it really impossible?
• how can it be proven that it is impossible (if it's impossible)

[EDIT]: After posting this question, and seeing how it was easy for people to solve it, I noticed that I posted the wrong drawing. The actual one is eaxctly like that but with triangles on all sides, not only top and bottom. As it would make the current answers invalid, I didn't replace the picture.

Answer 1

It is possible, and it's actually quite easy. Start on the red dot and move your pen according to numbers in a picture below.

Answer 2

Yes it is possible. With problems like these, look at all intersection points of segments. If there are $0$ or $2$ intersections where an odd number of segments join (including endpoints which are considered $1$ segment), then the task is doable. If more than $2$, it is not. Your drawing is definitely doable since all intersections involve $2$ or $4$ segments joining.

Similar problems have plagued my existence since third grade. One day I stumbled across a book on it when I was eleven or twelve and it provided a similar explanation to what I typed above.

Answer 3

It is possible.

Label the top vertex of the triangle at the top 1, the top-left vertex of the square 2, the top-right of the square 3, the bottom left of the square 4, the bottom right of the square 5, and the bottom vertex of the triangle on the bottom 6. The path is:

3 1 2 3 4 6 5 2 4 5 3.

Answer 4

Here is one way, out of many.

As you can see, I started at one vertex and ended at the same vertex. Since the graph is connected, and every vertex has an even number of segments joined to it, you can start at any vertex and end there, covering all the segments.

Answer 5

Look at each vertex where lines meet. Count how many lines meet there. Is that number odd or even? For each vertex with an odd number of lines (a vertex of odd-degree) when you draw the diagram you will have to start or end there. If there are more than two such vertexes you can not draw the diagram with just one line.

Since this diagram has no vertexes of odd-degree you can start drawing anywhere (including in the middle of a line) and still be able to complete the drawing. Just do not return to your starting place until you have drawn all the other lines.

Answer 6

A little theory:

Think of the figure as a graph, with vertices and edges as indicated in Wojowu's answer.

The graph is connected and every vertex has even degree (number of edges coming out of it), and therefore, by a theorem of graph theory, the graph has an Eulerian cycle. This means not only can you trace it without lifting your pen, but that you can do so in such a way that each edge is crossed only once, and also that you end where you began! Rory's answer shows one way this can be done.

Here's a related question for you: What if we don't care about crossing every edge, but we want to trace within the figure so that we meet each vertex exactly once, and we start and end at the same vertex? Can this be done? That is, does the graph have a Hamiltonian cycle?

Answer 7

It should only take 10 steps with an intersection at the middle, this is not a retracing.

Answer 8

In mathematics, drawing a geometric shape without lifting the pen and without tracing the same line more than once is identical to finding a Eulerian trail in the undirected graph composed by the intersections of the shape.

The existence of an Eulerian trail in a connected graph is directly linked to the number of vertices which have an odd degree (the degree of a vertex is the number of segments in the intersection) :

• If there are 0, then there exists at least one Eulerian cycle, which is an Eulerian trail which starts and ends at the same vertex. Such a graph is called an Eulerian graph.
• If there are 2, then there exists at least one Eulerian trail.
• All other numbers means there are no Eulerian trail at all, meaning that the drawing is not possible under these restrictions.

---

In your case, the graph is connected and all your vertices have an even degree, meaning that your problem is solvable. Here is one solution:

---

Another example, look at this this shape.

There are 4 vertices which have an odd degree.

So there's no solution for this one.

Answer 9

You've been told many solutions and how to identify a graph where it is possible. Here's an algorithm that will give you a solution to this type of puzzle whenever one exists. As bonus, you'll not even have to seek for a node with odd number of edges if one exists. However you'll have to remember the current partial path.

Start at an arbitrary vertex (that is, at an arbitrary intersection). Draw until you get stuck. This gives you the initial path.

Now there are several possibilities:

1. You've drawn the figure completely. Congratulations, you've solved the puzzle!

2. You got stuck at a different vertex than you started at, and the starting vertex still has not yet drawn edges. Then just draw the path you've found so far in reverse (that is, starting where you got stuck, and ending at you original starting point), and then continue until you get stuck again. Repeat until you either solved the puzzle, or found it unsolvable.

3. You got stuck at a different vertex than you started at, and the starting vertex has all edges already drawn. In that case draw the path you've found so far until you get to a vertex that has not yet all adjacent edges drawn (if none exists, the puzzle doesn't have a solution). Then go detour using only edges you did not use previously, until that's no longer possible. When you get stuck with this, there are two possibilities:

   • You got back to where you started the detour. Then follow the original path again until you either get to the next vertex with still not-yet-drawn edges on it (doing a detour as described above for each such vertex), or get to the end of the path (at which point you repeat the whole process with the path you've got now).

   • You got stuck somewhere else. Then there's no solution to the puzzle.

4. You got back at the vertex you started at, so you made a round trip (the vertex you ended at clearly has no not-yet-drawn edges as otherwise you wouldn't have gotten stuck). Start that round trip instead at one of the vertices that have not-yet-drawn edges (if there are no such vertices, the graph is not connected and thus not solvable). After finishing that round trip that way, you're no longer stuck and can continue. When you get stuck, start the process again with the new path.

Answer 10

Just for fun, I have had a look at all possible solutions.

• Starting from the central square, I get 176 solutions from each vertex of it.
• Starting from either the top or the bottom, I get 88 solutions for each.
• Overall there are 880 solutions.

Using the numbering of vertices shown here, the full list of solutions can be found here.