37
$\begingroup$

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

enter image description here

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.

$\endgroup$
15
  • 6
    $\begingroup$ Do you know anything about graph theory? $\endgroup$
    – Riley
    Commented Dec 31, 2015 at 14:58
  • 21
    $\begingroup$ Every vertex is even degree, so graph has an Euler tour. $\endgroup$
    – Cloverr
    Commented Dec 31, 2015 at 15:05
  • 4
    $\begingroup$ See en.wikipedia.org/wiki/Eulerian_path. $\endgroup$
    – Martín-Blas Pérez Pinilla
    Commented Dec 31, 2015 at 16:21
  • 24
    $\begingroup$ This took me 5 seconds. You should at least attempt to solve it before asking the question... $\endgroup$
    – math_lover
    Commented Dec 31, 2015 at 22:01
  • 3
    $\begingroup$ I rolled the question back to its previous form, before the author added a second shape; we generally discourage edits to questions that change their meaning especially if they invalidate existing answers. Posting a new question would be appropriate, and you may include a link to this question in the new one (and the other way around) - especially since the answer is rather different in that case. $\endgroup$
    – Milo Brandt
    Commented Jan 1, 2016 at 21:49

12 Answers 12

Reset to default
67
$\begingroup$

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.

enter image description here

$\endgroup$
12
  • 26
    $\begingroup$ Nice. Exchanging $9$ and $11$ also leads to a solution which may be considered easier to draw (fewer "bends"). $\endgroup$
    – chi
    Commented Dec 31, 2015 at 15:24
  • 5
    $\begingroup$ @chi On the other hand Wojowu's solution satisfies the additional constraint of not crossing any edges (it was not a requirement here but sometimes is in puzzles like this.) $\endgroup$
    – JohannesD
    Commented Dec 31, 2015 at 16:24
  • 1
    $\begingroup$ I wouldn't call it that much "easy". The "bend at the centre" (path 8 to 9 on your image) can make it tricky, as probably the temptation is to follow the straight lines all the way through. Are there solutions that don't "bend on the center"? (I have not even tried, I admit) $\endgroup$
    – Rolazaro Azeveires
    Commented Dec 31, 2015 at 17:43
  • 4
    $\begingroup$ @RolazaroAzeveires Look at chi's comment. Swapping 9 and 11 makes such a solution. $\endgroup$
    – Wojowu
    Commented Dec 31, 2015 at 17:56
  • 1
    $\begingroup$ @JohannesD: No, because either the cross occurs at a vertex which divides the line (11-8) anyway; or you cross the same edges here as well. chi is absolutely correct, and the suggestion does not introduce or remove any edge crossing that wasn't there already. $\endgroup$
    – Asaf Karagila ♦
    Commented Dec 31, 2015 at 19:11
29
$\begingroup$

Here is one way, out of many.

enter image description here

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.

$\endgroup$
23
$\begingroup$

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:

Problem solved!

Another example, look at this this shape.

Another shape

There are 4 vertices which have an odd degree.

No solution.

So there's no solution for this one.

$\endgroup$
6
  • 1
    $\begingroup$ You omitted an important (but obvious) condition: The graph must be connected! $\endgroup$
    – celtschk
    Commented Jan 2, 2016 at 17:12
  • 1
    $\begingroup$ @celtschk: Good point! $\endgroup$
    – Benoit Esnard
    Commented Jan 3, 2016 at 19:08
  • 1
    $\begingroup$ neat graphic, I would love to know how you made that gif? $\endgroup$
    – Matt
    Commented Oct 20, 2017 at 10:21
  • 2
    $\begingroup$ @Matt: I saved the image in the question, and edited it to remove one vertex at a time, saving as another picture each time. Then I searched a wesbite to make a GIF from multiple images. I don't remember which one I've used since this answer is quite old now. $\endgroup$
    – Benoit Esnard
    Commented Oct 20, 2017 at 12:17
  • 2
    $\begingroup$ @Matt: that's indeed quite manual, but there are scripts to "merge" multiple images into an animated GIF. $\endgroup$
    – Benoit Esnard
    Commented Oct 23, 2017 at 9:17
21
$\begingroup$

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.

$\endgroup$
3
  • 4
    $\begingroup$ Well, here we have only vertices of even degree, and this is necessary and sufficient for the existence of an Euler tour (path returning to the starting vertex). $\endgroup$
    – tomglabst
    Commented Dec 31, 2015 at 15:10
  • $\begingroup$ My initial comment was due to the inclusion of $1$ as an option for the number of odd-degree vertices. $\endgroup$
    – Cameron Buie
    Commented Dec 31, 2015 at 18:10
  • $\begingroup$ I realized soon after my post that such a circuit was impossible an corrected it. Thank you. $\endgroup$
    – Leonidas Lanier
    Commented Dec 31, 2015 at 18:59
14
$\begingroup$

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?

$\endgroup$
2
  • 1
    $\begingroup$ This particular graph has a pretty straightforward Hamiltonian cycle (regardless of whether the centre of the X is actually a vertex or not). $\endgroup$
    – Stack Exchange Supports Israel
    Commented Jan 2, 2016 at 7:46
  • 1
    $\begingroup$ @immibis right. it's just something I thought the original poster might want to think about, then maybe think about types of graphs with only one type of cycle, etc $\endgroup$
    – Forever Mozart
    Commented Jan 2, 2016 at 9:21
6
$\begingroup$

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

enter image description here

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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.

  1. 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.
$\endgroup$
3
$\begingroup$

I have found it on my second try. It took less than 30 seconds to find the answer. Maybe i was lucky?

enter image description here

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
2
  • 2
    $\begingroup$ Hi, not sure if you knew it : en.wikipedia.org/wiki/BEST_theorem $\endgroup$
    – reuns
    Commented Jan 3, 2016 at 0:54
  • $\begingroup$ I did not! Thanks! :) $\endgroup$
    – SSF
    Commented Jan 3, 2016 at 2:09
1
$\begingroup$

Concept - If a graph is connected and Degree of every vertex is even ,then it has an eulerian walk.

By connected I mean that there must be a way to reach any vertex from any vertex ( they may not have direct edge ). Degree of vertex means the number of edges which are passing through it.

So in your question , degree of every vertex is even and the graph is connected , it means it has a eulerian walk. So we can traverse the whole figure without lifting the pen once !

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .