Mathematics for Computer Science

Chapter 12 Planar Graphs372

graph withvGCvHvertices,eGCeHC 1 edges, andfGCfH 1 faces. Since

.vGCvH/.eGCeHC1/C.fGCfH1/

D.vGeGCfG/C.vHeHCfH/ 2

D.2/C.2/ 2 (by structural induction hypothesis)

D2;

veCf remains equal to 2 for the constructed embedding. That is,P.e/also

holds in this case.

This completes the proof of the constructor cases, and the theorem follows by

structural induction. 

12.4 Bounding the Number of Edges in a Planar Graph

Like Euler’s formula, the following lemmas follow by structural induction directly

from Definition 12.2.2.

Lemma 12.4.1. In a planar embedding of a connected graph, each edge occurs

once in each of two different faces, or occurs exactly twice in one face.

Lemma 12.4.2. In a planar embedding of a connected graph with at least three

vertices, each face is of length at least three.

Combining Lemmas 12.4.1 and 12.4.2 with Euler’s Formula, we can now prove

that planar graphs have a limited number of edges:

Theorem 12.4.3. Suppose a connected planar graph hasv 3 vertices ande

edges. Then

e3v6: (12.2)

Proof. By definition, a connected graph is planar iff it has a planar embedding. So

suppose a connected graph withvvertices andeedges has a planar embedding

withf faces. By Lemma 12.4.1, every edge has exactly two occurrences in the

face boundaries. So the sum of the lengths of the face boundaries is exactly2e.

Also by Lemma 12.4.2, whenv 3 , each face boundary is of length at least three,

so this sum is at least3f. This implies that

3f 2e: (12.3)