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

|E|=|T|+|T|=(|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