16
$\begingroup$

Can you determine if it's possible to draw a geometric figure (made up from shapes like rectangles, triangles, and other regular shapes) with one pen stroke and not drawing the same line twice.

I am thinking about something related to graph theory or something like that.

For example, something like this:

enter image description here

$\endgroup$
  • $\begingroup$ Seven Bridges of Königsberg $\endgroup$ – KSmarts Apr 24 '15 at 21:33
  • $\begingroup$ Welcome to Puzzling StackExchange. Nice Puzzle but here this is going to be solved within minutes. $\endgroup$ – The Dark Truth Jul 28 '16 at 6:56
  • $\begingroup$ @f'' Good catch. I assume we'll want to get this question marked as a dupe and merged as soon as possible? $\endgroup$ – Dennis Meng Jul 28 '16 at 7:03
26
$\begingroup$

Yes! This is a classic graph theory problem. Anywhere where lines meet is called a vertex, and the degree of a vertex is the number of lines that meet there. Euler proved that as long as a graph has either 0 or 2 vertices of odd degree, and the graph is connected (consists of a single piece), then it can be drawn as you specified. Furthermore, if there are any odd vertices, then any successful Eulerian path (as such a pen stroke is called) must start at one, and end at the other.

The main reason this is true is as follows: every time you enter and leave a vertex, you kill two of its edges. So, if a vertex has an odd number of edges, not all of its edges can be taken care of by passing through it, so the pen must start or end there. There are only two start and end points, so there can be at most two odd degree vertices.

In your picture, there is a square with horizontal sides, all of whose vertices have 5 edges coming out of them. This means that you have $4$ odd-degree vertices, which is $2$ too many, so your graph can't be drawn with a single non-overlapping pen stroke. But, if you erased one of the diagonals of this middle square, then you'd be in business.

This result applies to any shape with various curves on a page which meet at various places, not just straight line figures.

$\endgroup$
  • $\begingroup$ You could say "it can be drawn with a pen when the sum of the degrees of the vertices in the graph is even" $\endgroup$ – d'alar'cop Apr 23 '15 at 2:48
  • 2
    $\begingroup$ @d'alar'cop The sum of the degrees of the vertices of every graph is even. In fact, $\sum \deg v=2E$, where $E$ is the number of edges. $\endgroup$ – Mike Earnest Apr 23 '15 at 2:53
  • $\begingroup$ you are right. how foolish of me :) $\endgroup$ – d'alar'cop Apr 23 '15 at 5:26
  • 1
    $\begingroup$ I'd like to add the obvious condition is that the graph is connected, i.e., there is a path between each pair of vertices. When drawing the path (removing edges), you must take care that you don't accidentally create disconnected parts to the graph. $\endgroup$ – JiK Apr 23 '15 at 13:44
  • $\begingroup$ @Jik excellent point, forgot about that $\endgroup$ – Mike Earnest Apr 23 '15 at 13:55
5
$\begingroup$

What you are asking for is how to find an "Eulerian path"

This page explains it quite well:

https://www.math.ku.edu/~jmartin/courses/math105-F11/Lectures/chapter5-part2.pdf

Also, there's this page:

http://www.ctl.ua.edu/math103/euler/howcanwe.htm

Which, says, to paraphrase:

If there's 0 odd vertexes then there's at least an Eulerian circuit, an Eulerian path that ends where it begins, if there's 2 odd vertexes there's at least an Eulerian path. Anything else has no paths or circuits.

$\endgroup$
4
$\begingroup$

In your picture, there is a square with horizontal sides, all of whose vertices have 5 edges coming out of them. This means that you have 4 odd-degree vertices, which is 2 too many, so your graph can't be drawn with a single non-overlapping pen stroke. But, if you erased one of the diagonals of this middle square, then you'd be in business. --Mike Earnest

And such a path would look like :

enter image description here

$\endgroup$
2
$\begingroup$

Answer:

This is impossible. The question asks for the existence of a Eulerian path. For this to work, exactly zero or two vertices must have an odd degree, but here, the four corners of the squares have an odd degree. Also related to Seven Bridges of Königsberg problem.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.