Here's a proof
of this theorem
. But first, if you really
to think you're a mathematician
, you have to use the right jargon
. So we'll call the "figure
" a graph
, the "point
, and the "line
. 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 component
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 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.
- 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.
- 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").