proof of Euler's polyhedron theorem

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 $G=(V,E)$ be a planar graph; we consider some particular planar embedding of $G$ . Let $F$ be the set of faces of this embedding. Also let $G'=(F,E')$ be the dual graph ($E'$ contains an edge between any 2 adjacent faces of $G$ ). The planar embeddings of $G$ and $G'$ determine a correspondence between $E$ and $E'$ : two vertices of $G$ are adjacent iff they both belong to a pair of adjacent faces of $G$ ; denote by $\phi:E\to E'$ this correspondence.

In all illustrations, we represent a planar graph $G$ , and the two sets of edges $T\subseteq E$ (in red) and $T'\subseteq E'$ (in blue).

Let $T\subseteq E$ be a spanning tree of $G$ . Let $T' = E' \setminus \phi[E]$ . We claim that $T'$ is a spanning tree of $G'$ . Indeed,

$T'$ contains no loop.

Given any loop of edges in $T'$ , we may draw a loop on the faces of $G$ which participate in the loop. This loop must partition the vertices of $G$ into two non-empty sets, and only crosses edges of $E\setminus T$ . Thus, $(V,T)$ has more than a single connected component, so $T$ is not spanning. [The proof of this utilizes the Jordan curve theorem.]

$T'$ spans $G'$ .

For suppose $T'$ does not connect all faces $F$ . Let $f_1,f_2\in F$ be two faces with no path between them in $T'$ . Then $T$ must contain a cycle separating $f_1$ from $f_2$ , and cannot be a tree. [The proof of this utilizes the Jordan curve theorem.]

We thus have a partition $E=T\cup \phi^{-1}[T']$ of the edges of $G$ into two sets. Recall that in any tree, the number of edges is one less than the number of vertices. It follows that$$ |E| = |T| + |T'| = (|V|-1) + (|F|-1) = |V|+|F|-2,$$ as required.