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 $\varphi :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 \varphi [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 nonempty 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 {\varphi}^{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}=(V1)+(F1)=V+F2,$$ 
as required.
Title  Euler’s polyhedron theorem, proof of 

Canonical name  EulersPolyhedronTheoremProofOf 
Date of creation  20130322 12:47:36 
Last modified on  20130322 12:47:36 
Owner  mps (409) 
Last modified by  mps (409) 
Numerical id  7 
Author  mps (409) 
Entry type  Proof 
Classification  msc 05C99 