208 13. Coloring Maps and Graphs
because a planar graph can have points of degree higher than 5 (the “dual”
graph in Figure 13.9 has a point of degree 7, for example). But if you solved
the exercises, you may recall that we don’t have to assume thatallnodes
of the graph have degree at most 5. The same procedure as used in the
proof of Theorem 13.3.1 gives a 6-coloring if we know that the graph has
at least onepoint of degree 5 or less, and so do all its subgraphs (Exercise
13.3.4). Is this condition applicable here?
The answer is yes:
Lemma 13.4.3Every planar graph has a point of degree at most 5.
Proof. This lemma follows from Euler’s Formula. In fact, we only need a
consequence of Euler’s Formula, namely, Theorem 12.2.2:A planar graph
withnnodes has at most 3 n− 6 edges.
Assume that our graph violates Lemma 13.4.3, and so every node has
degree at least 6. Then counting the edges node by node, we count at least
6 nedges. Each edge is counted twice, so the number of edges is at least 3n,
contradicting Theorem 12.2.2.
Since the subgraphs of a planar graph are planar as well, it follows that
they too have a point of degree at most 5, and so Exercise 13.3.4 can be
applied, and we get that every planar graph is 6-colorable.
So we have proved the “Six Color Theorem.” We want to shave off 1
color from this result (how nice it would be to shave off 2!). For this, we
use the same procedure of coloring points one by one again, together with
Lemma 13.4.3; but we have to look at the procedure more carefully.
Proof[of the Five Color Theorem]. So, we have a planar graph withn
nodes. We use induction on the number of nodes, so we assume that planar
graphs with fewer thannnodes are 5-colorable. We also know that our
graph has a nodevwith degree at most 5.
Ifvhas degree 4 or less, then the argument is easy: Let us deletevfrom
the graph, and color the remaining graph with 5 colors (which is possible
by the induction hypothesis, since this is a planar graph with fewer nodes).
The nodevhas at most 4 neighbors, so we can find a color forvthat is
different from the colors of its neighbors, and extend the coloring tov.
So the only difficult case occurs when the degree ofvis exactly 5. Let
uandwbe two neighbors ofv. Instead of just deletingv, we change the
graph a bit more: We use the place freed up by the deletion ofvto merge
uandwto a single point, which we calluw. Every edge that entered either
uorwwill be redirected to the new nodeuw(Figure 13.10).
This modified graph is planar and has fewer nodes, so it can be colored
with 5 colors by the induction hypothesis. If we pull the two pointsuandw
apart again, we get a coloring of all nodes ofGexceptvwith 5 colors. What
we gained by this trick of merginguandwis that in this coloring they
have the same color! So even thoughvhas 5 neighbors, two of those have