Euler's Formula, Proof 20: Euler Tours

Given the similarity of names between an Euler tour (a closed walk in a graph that visits every edge exactly once) and Euler's formula, it is surprising that a strong connection between the two came so recently. The proof below is based on a relation between repetitions and face counts in Eulerian planar graphs observed by Red Burton, a version of the Graffiti software system for making conjectures in graph theory.

A planar graph $G$ has an Euler tour if and only if the degree of every vertex in $G$ is even. Given such a tour, let $R$ denote the number of times the tour reaches a vertex that has already been seen earlier in the tour. For instance, this repetition count would equal one for a graph in the form of a single cycle: only the starting vertex is repeated. As Red Burton observed, it is always the case that $F=R+1$. For, if one draws the edges of the graph in the order given by the tour, then the drawing starts out with one face, and every repeated vertex closes off one more face. But we also have $R=E-V+1$, because there are $E+1$ vertices visited in the tour from start to end, of which $V$ are not repetitions. Putting these two equations for $R$ together and eliminating $R$ gives Euler's formula, but only for Eulerian graphs.

Now, given an arbitrary planar graph $G$, draw two parallel copies of each edge, separated by a thin two-sided face. This modification doesn't change the value of the formula $V-E+F$ for graph $G$, because it adds the same quantity $E$ to both the number of edges and the number of faces, which cancel each other in the formula. But the new graph is Eulerian, so the repetition count argument for Eulerian graphs applies to it, and shows that in it $E-V+F=2$. The same must be true in the original graph.

The idea of proving Euler's formula by transforming an arbitrary planar graph to make it Eulerian was found by University of Houston chemical engineering sophomore Stephanie Mathew, under the supervision of Siemion Fajtlowicz, who used this idea to find the above proof. Fajtlowicz also supplies two different variants of the proof, in which one repeatedly connects pairs of odd vertices either by an arc in the plane that avoids all the existing vertices or by by doubling paths in the given graph. Both of these alternative versions of the Euler tour proof use the fact that every graph has an even number of odd vertices, which was proven by Euler.

Proofs of Euler's Formula.
From the Geometry Junkyard, computational and recreational geometry pointers.
David Eppstein, Theory Group, ICS, UC Irvine.