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