12.8. Classifying Polyhedra 377
Every planar graph withvvertices is five-colorable.
Base cases(v 5 ): immediate.
Inductive case: SupposeGis a planar graph withvC 1 vertices. We will describe
a five-coloring ofG.
First, choose a vertex,g, ofGwith degree at most 5; Lemma 12.7.1 guarantees
there will be such a vertex.
Case 1: (deg.g/ < 5): DeletinggfromGleaves a graph,H, that is planar by
Lemma 12.6.3, and, sinceHhasvvertices, it is five-colorable by induction
hypothesis. Now define a five coloring ofGas follows: use the five-coloring
ofHfor all the vertices besidesg, and assign one of the five colors togthat
is not the same as the color assigned to any of its neighbors. Since there are
fewer than 5 neighbors, there will always be such a color available forg.
Case 2: (deg.g/D 5 ): If the five neighbors ofginGwere all adjacent to each
other, then these five vertices would form a nonplanar subgraph isomorphic
toK 5 , contradicting Lemma 12.6.3 (sinceK 5 is not planar). So there must
be two neighbors,n 1 andn 2 , ofgthat are not adjacent. Now mergen 1 and
ginto a new vertex,m. In this new graph,n 2 is adjacent tom, and the graph
is planar by Lemma 12.6.4. So we can then mergemandn 2 into a another
new vertex,m^0 , resulting in a new graph,G^0 , which by Lemma 12.6.4 is
also planar. SinceG^0 hasv 1 vertices, it is five-colorable by the induction
hypothesis.
Now define a five coloring ofGas follows: use the five-coloring ofG^0 for
all the vertices besidesg,n 1 andn 2. Next assign the color ofm^0 inG^0 to
be the color of the neighborsn 1 andn 2. Sincen 1 andn 2 are not adjacent
inG, this defines a proper five-coloring ofGexcept for vertexg. But since
these two neighbors ofghave the same color, the neighbors ofghave been
colored using fewer than five colors altogether. So complete the five-coloring
ofGby assigning one of the five colors togthat is not the same as any of
the colors assigned to its neighbors.
12.8 Classifying Polyhedra
The Pythagoreans had two great mathematical secrets, the irrationality of
p
2 and
a geometric construct that we’re about to rediscover!
