12.3. Euler’s Formula 371
12.3 Euler’s Formula
The value of the recursive definition is that it provides a powerful technique for
proving properties of planar graphs, namely, structural induction. For example,
we will now use Definition 12.2.2 and structural induction to establish one of the
most basic properties of a connected planar graph, namely, that the number of ver-
tices and edges completely determines the number of faces in every possible planar
embedding of the graph.
Theorem 12.3.1(Euler’s Formula).If a connected graph has a planar embedding,
then
v eCf D 2
wherevis the number of vertices,eis the number of edges, andfis the number of
faces.
For example, in Figure 12.5,vD 4 ,eD 6 , andfD 4. Sure enough, 4 6 C 4 D
2 , as Euler’s Formula claims.
Proof. The proof is by structural induction on the definition of planar embeddings.
LetP.E/be the proposition thatv eCf D 2 for an embedding,E.
Base case(Eis the one-vertex planar embedding): By definition,vD 1 ,eD 0 ,
andf D 1 , soP.E/indeed holds.
Constructor case(split a face): SupposeGis a connected graph with a planar
embedding, and supposeaandbare distinct, nonadjacent vertices ofGthat appear
on some discrete face, Da:::ba, of the planar embedding.
Then the graph obtained by adding the edgeha—bito the edges ofGhas a
planar embedding with one more face and one more edge thanG. So the quantity
v eCf will remain the same for both graphs, and since by structural induction
this quantity is 2 forG’s embedding, it’s also 2 for the embedding ofGwith the
added edge. SoPholds for the constructed embedding.
Constructor case(add bridge): SupposeGandHare connected graphs with pla-
nar embeddings and disjoint sets of vertices. Then connecting these two graphs
with a bridge merges the two bridged faces into a single face, and leaves all other
faces unchanged. So the bridge operation yields a planar embedding of a connected
