# 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 $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^{\prime}=(F,E^{\prime})$ be the dual graph ($E^{\prime}$ contains an edge between any 2 adjacent faces of $G$). The planar embeddings of $G$ and $G^{\prime}$ determine a correspondence between $E$ and $E^{\prime}$: two vertices of $G$ are adjacent iff they both belong to a pair of adjacent faces of $G$; denote by $\phi:E\to E^{\prime}$ this correspondence. In all illustrations, we represent a planar graph $G$, and the two sets of edges $T\subseteq E$ (in red) and $T^{\prime}\subseteq E^{\prime}$ (in blue).

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

$T^{\prime}$ contains no loop. Given any loop of edges in $T^{\prime}$, 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^{\prime}$ spans $G^{\prime}$. For suppose $T^{\prime}$ does not connect all faces $F$. Let $f_{1},f_{2}\in F$ be two faces with no path between them in $T^{\prime}$. 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^{\prime}]$ 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^{\prime}|=(|V|-1)+(|F|-1)=|V|+|F|-2,$

as required.

Title Euler’s polyhedron theorem, proof of EulersPolyhedronTheoremProofOf 2013-03-22 12:47:36 2013-03-22 12:47:36 mps (409) mps (409) 7 mps (409) Proof msc 05C99