Now we return to the original graph coloring problem: coloring maps. As indicated in section 1.1, the map coloring problem can be turned into a graph coloring problem. Figure 5.10.1 shows the example from section 1.1.

Figure 5.10.1. A map and its corresponding graph.

Graphs formed from maps in this way have an important property: they are planar.

Definition 5.10.1 A graph $G$ is planar if it can be represented by a drawing in the plane so that no edges cross. $\square$

Note that this definition only requires that some representation of the graph has no crossing edges. Figure 5.10.2 shows two representations of $K_4$; since in the second no edges cross, $K_4$ is planar.

Figure 5.10.2. $K_4$ drawn in two ways; the second shows that it is planar.

The number of colors needed to properly color any map is now the number of colors needed to color any planar graph. This problem was first posed in the nineteenth century, and it was quickly conjectured that in all cases four colors suffice. This was finally proved in 1976 (see figure 5.10.3) with the aid of a computer. In 1879, Alfred Kempe gave a proof that was widely known, but was incorrect, though it was not until 1890 that this was noticed by Percy Heawood, who modified the proof to show that five colors suffice to color any planar graph. We will prove this Five Color Theorem, but first we need some other results. We assume all graphs are simple.

Figure 5.10.3. The postmark on University of Illinois mail after the Four Color Theorem was proved.

Theorem 5.10.2 (Euler's Formula) Suppose $G$ is a connected planar graph, drawn so that no edges cross, with $n$ vertices and $m$ edges, and that the graph divides the plane into $r$ regions. Then $$r=m-n+2.$$

Proof. The proof is by induction on the number of edges. The base case is $m=n-1$, the minimum number of edges in a connected graph on $n$ vertices. In this case $G$ is a tree, and contains no cycles, so the number of regions is 1, and indeed $1=(n-1)-n+2$.

Now suppose $G$ has more than $n-1$ edges, so it has a cycle. Remove one edge from a cycle forming $G'$, which is connected and has $r-1$ regions, $n$ vertices, and $m-1$ edges. By the induction hypothesis $r-1=(m-1)-n+2$, which becomes $r=m-n+2$ when we add 1 to each side. $\qed$

Lemma 5.10.3 Suppose $G$ is a simple connected planar graph, drawn so that no edges cross, with $n\ge3$ vertices and $m$ edges, and that the graph divides the plane into $r$ regions. Then $m\le 3n-6$.

Proof. Let $f_i$ be the number of edges that adjoin region number $i$; if the same region is on both sides of an edge, that edge is counted twice. We call the edges adjoining a region the boundary edges of the region. Since $G$ is simple and $n\ge3$, every region is bounded by at least 3 edges. Then $\sum_{i=1}^r f_i=2m$, since each edge is counted twice, once for the region on each side of the edge. From $r=m-n+2$ we get $3r=3m-3n+6$, and because $f_i\ge 3$, $3r\le \sum_{i=1}^r f_i=2m$, so $3m-3n+6\le 2m$, or $m\le 3n-6$ as desired. $\qed$

Theorem 5.10.4 $K_5$ is not planar.

Proof. $K_5$ has 5 vertices and 10 edges, and $10\not\le 3\cdot 5-6$, so by the lemma, $K_5$ is not planar. $\qed$

Lemma 5.10.5 If $G$ is planar then $G$ has a vertex of degree at most 5.

Proof. We may assume that $G$ is connected (if not, work with a connected component of $G$). Suppose that $\d(v_i)>5$ for all $v_i$. Then $2m=\sum_{i=1}^n \d(v_i)\ge 6n$. By lemma 5.10.3, $3n-6\ge m$ so $6n-12\ge 2m$. Thus $6n\le 2m \le 6n-12$, a contradiction. $\qed$

Theorem 5.10.6 (Five Color Theorem) Every planar graph can be colored with 5 colors.

Proof. The proof is by induction on the number of vertices $n$; when $n\le 5$ this is trivial.

Now suppose $G$ is planar on more than 5 vertices; by lemma 5.10.5 some vertex $v$ has degree at most 5. By the induction hypothesis, $G-v$ can be colored with 5 colors. Color the vertices of $G$, other than $v$, as they are colored in a 5-coloring of $G-v$. If $\d(v)\le 4$, then $v$ can be colored with one of the 5 colors to give a proper coloring of $G$ with 5 colors. So we now suppose $\d(v)=5$. If the five neighbors of $v$ are colored with four or fewer of the colors, then again $v$ can be colored to give a proper coloring of $G$ with 5 colors.

Now we suppose that all five neighbors of $v$ have a different color, as indicated in figure 5.10.4.

Figure 5.10.4. Five neighbors of $v$ colored with 5 colors: $v_1$ is red, $v_2$ is purple, $v_3$ is green, $v_4$ is blue, $v_5$ is orange.

Suppose that in $G$ there is a path from $v_1$ to $v_3$, and that the vertices along this path are alternately colored red and green; call such a path a red-green alternating path. Then together with $v$, this path makes a cycle with $v_2$ on the inside and $v_4$ on the outside, or vice versa. This means there cannot be a purple-blue alternating path from $v_2$ to $v_4$. Supposing that $v_2$ is inside the cycle, we change the colors of all vertices inside the cycle colored purple to blue, and all blue vertices are recolored purple. This is still a proper coloring of all vertices of $G$ except $v$, and now no neighbor of $v$ is purple, so by coloring $v$ purple we obtain a proper coloring of $G$.

If there is no red-green alternating path from $v_1$ to $v_3$, then we recolor vertices as follows: Change the color of $v_1$ to green. Change all green neighbors of $v_1$ to red. Continue to change the colors of vertices from red to green or green to red until there are no conflicts, that is, until a new proper coloring is obtained. Because there is no red-green alternating path from $v_1$ to $v_3$, the color of $v_3$ will not change. Now no neighbor of $v$ is colored red, so by coloring $v$ red we obtain a proper coloring of $G$. $\qed$

Exercises 5.10

Ex 5.10.1 Show $K_{3,3}$ is not planar. (Prove a lemma like lemma 5.10.3 for bipartite graphs, then do something like the proof of theorem 5.10.4.) What is the chromatic number of $K_{3,3}$?