Euler’s polyhedron theorem, proof of
This proof is not one of the standard proofs given to Euler’s formula. I found the idea presented in one of Coxeter’s books. It presents a different approach to the formula, that may be more familiar to modern students who have been exposed to a “Discrete Mathematics” course. It falls into the category of “informal” proofs: proofs which assume without proof certain properties of planar graphs
usually proved with algebraic topology. This one makes deep (but somewhat hidden) use of the Jordan curve theorem.
Let be a planar graph; we consider some particular planar embedding of . Let be the set of faces of this embedding. Also let be the dual graph ( contains an edge between any 2 adjacent faces of ). The planar embeddings of and determine a correspondence between and : two vertices of are adjacent iff they both belong to a pair of adjacent faces of ; denote by this correspondence.
In all illustrations, we represent a planar graph , and the two sets of edges (in red) and (in blue).
Let be a spanning tree of . Let . We claim that is a spanning tree of . Indeed,
- contains no loop.
Given any loop of edges in , we may draw a loop on the faces of which participate in the loop. This loop must partition
the vertices of into two non-empty sets, and only crosses edges of . Thus, has more than a single connected component
, so is not spanning.[The proof of this utilizes the Jordan curve theorem.]
- spans .
For suppose does not connect all faces . Let be two faces with no path between them in . Then must contain a cycle separating from , and cannot be a tree.[The proof of this utilizes the Jordan curve theorem.]
We thus have a partition of the edges of into two sets. Recall that in any tree, the number of edges is one less than the number of vertices. It follows that
as required.