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 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 {\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 }|=(|V|-1)+(|F|-1)=|V|+|F|-2,$$

as required.

Title	Euler’s polyhedron theorem, proof of
Canonical name	EulersPolyhedronTheoremProofOf
Date of creation	2013-03-22 12:47:36
Last modified on	2013-03-22 12:47:36
Owner	mps (409)
Last modified by	mps (409)
Numerical id	7
Author	mps (409)
Entry type	Proof
Classification	msc 05C99