Euler’s polyhedron theorem, proof of

This proof is not one of the standard proofs given to Euler’s formulaMathworldPlanetmathPlanetmath. 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 graphsMathworldPlanetmath 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 embeddingMathworldPlanetmathPlanetmath. 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 ϕ:EE this correspondence.

In all illustrations, we represent a planar graph G, and the two sets of edges TE (in red) and TE (in blue).

Let TE be a spanning treeMathworldPlanetmath of G. Let T=Eϕ[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 partitionMathworldPlanetmathPlanetmath the vertices of G into two non-empty sets, and only crosses edges of ET. Thus, (V,T) has more than a single connected componentMathworldPlanetmathPlanetmathPlanetmathPlanetmath, 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 f1,f2F be two faces with no path between them in T. Then T must contain a cycle separating f1 from f2, and cannot be a tree. [The proof of this utilizes the Jordan curve theorem.]

We thus have a partition E=Tϕ-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


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