How to tell whether a figure can be drawn in one stroke

You've probably seen the type of puzzle which asks you to draw a certain pattern without lifting your pen from the page or going over any line twice; probably the most famous one is this:

  /\
 /  \
/____\
|\  /|
| \/ |
| /\ |
|/__\|

An interesting question is this: given a certain figure, how can one tell whether it's possible to draw it in one continuous stroke? The answer is quite simple; I think Euler may have been the mathematician to discover this, probably in relation to his study of the Bridges of Konisberg problem:

Look at all the vertices in the pattern. Count how many lines meet at each vertex, and note whether the number is even or odd. Count how many vertices have an odd number of lines going into them. If there are more than two of these "odd" vertices, then the figure cannot be drawn without lifting one's pen; otherwise, it can. For example, in the figure above, there are only two odd vertices (the bottom corners, which each have three lines going into them), so we know it's possible to draw in one stroke.

A couple more interesting facts: the number of odd vertices is always even (it can be zero, but zero's an even number as far as most mathematicians are concerned). If there are no odd vertices in the figure, then you may begin drawing at any point in the pattern. If there are two odd vertices, then you must begin drawing at one of them and end at the other (so for the picture above, every method of drawing it (and there are many) involves beginning at one of the bottom corners and ending at the other).

Here's a proof of this theorem of Euler. But first, if you really want people to think you're a mathematician, you have to use the right jargon. So we'll call the "figure" a graph, the "points" vertices, and the "lines" edges. If we agree that strokes must start and end at a point (sorry, vertex), a "stroke" is a connected list of vertices (i.e. a list of the vertices that it visits, such that an edge connects every adjacent pair of vertices). And we'll call such a list a path. A path is closed if it starts and ends at the same vertex. One more thing: serious mathematicians don't "count how many lines meet at a vertex"; they compute the degree of the vertex. But it's the same thing, of course. And one more thing: the graph must itself be connected: it must be possible to have a path going from any vertex to any other vertex; otherwise, we could just take the union of 2 graphs which can each be covered by a path; the degrees meet the criterion, but obviously the graph can't be drawn in one stroke, because it has 2 separate components.

The advantage of using all this jargon is that we'll be able to say we're proving an important theorem in graph theory (rather than mucking about with drawing stick figures on the blackboard).

What jt and Euler are saying is that a graph may be drawn in one stroke (sorry, is covered by a single path which repeats no edge twice) iff (if and only if) it has precisely 0 or 2 vertices of odd degree. To show this, we have to show that if a graph can be drawn in one stroke then there are 0 or 2 vertices of odd degree, and conversely that if there are 0 or 2 vertices of odd degree then the graph may be drawn in one stroke.

1. Suppose the graph may be covered by a single path which repeats no edge twice. Look at any vertex of this path except for the first or last vertex (an interior vertex). Every time the path enters the vertex, it also has to leave (because it's not the last vertex on the path); and every time the path leaves the vertex, it must have arrived just before (because it's not the first vertex on the path). And every edge connected to this vertex is covered exactly once by the path, we've just shown that the degree of every interior vertex must be even.

   Now, if the path is closed, it has one "first" vertex, which is also its last vertex. All other edges of the path are of even degree. But we could equally have chosen any other vertex of the path to be "first", so we've shown that all vertices have even degree (if the graph has just one vertex, this argument does not work; but then the graph just contains loops around that vertex, and every loop adds 2 to the degree). So if the path is closed all vertices have even degree.

   Otherwise, the path has distinct first and last vertices. The above argument shows that except for the first edge of the path, which leaves the first vertex, the number of edges at the first vertex is even. So counting that first edge, we have that the degree of the first vertex is odd. And the same argument "in reverse" shows that the degree of the last vertex is odd, too.

2. Now suppose the degrees are all even, except maybe for precisely 2 vertices. We'll show how to draw a path which covers each edge precisely once. The proof is by induction on the number of edges.

   If the graph has exactly 1 edge, then it must look like this:

   *---*
   

   and the path between the 2 vertices consisting of that single edge covers the graph.

   Now suppose the graph has more than one edge.

   • If all degrees are even, pick any vertex as the first vertex of the path, and pick any edge leaving it as the first edge of the path. If we remove that edge, we'll be left with a graph with 2 vertices of odd degree: the first vertex u we picked, and the opposite end v of the edge we picked (if the edge is a loop, they're the same vertex, and all degrees remain even; but let's just ignore loops, since they're anyway easy to deal with). By our induction hypothesis (we have one less edge!), we can cover the remaining edges by a path which starts at v and ends at u; prefixing our chosen edge at the beginning of this path gives us a path that covers all edges.
   • Otherwise, 2 degrees are odd. Pick one of the vertices with odd degree, and pick any edge leaving it, except do not pick an edge leading to the other vertex of odd degree if that vertex's degree is 1, and do not pick an edge the removal of which leaves the graph disconnected. We can do this, because we have more than one edge, and because we start out with a connected graph (this requires some thought; the idea is to show that there can be at most 1 "bad" edge at a vertex, and that if there is a bad edge, it cannot be the only edge at that vertex). Now remove this edge from the graph; ignoring the possibility of loops, you've made the degree of your starting vertex even; either the edge you picked lead to the other vertex of odd degree, and then you're left with all vertices of even degree, or else the other vertex of odd degree keeps its odd degree, and the other end of the chosen edge moves from even degree to odd degree, so you're left with 2 vertices of odd degree. In both cases, the induction hypothesis is applicable, and gluing the chosen edge at the start of the path guaranteed by the induction hypothesis shows the theorem.

---

It is interesting to note, by contrast, that the corresponding question for vertices, does there exist a path which covers each vertex precisely once, is known as the Hamiltonian path problem (unlike this Eulerian path problem), and is known to be NP complete (or in plain English, "very very hard").