Chapter 7c


The Four Color Theorem and Maps


Technical Terms:

adjacent, color, dual graph, loop, planar, Schlegel diagram, tetrahedron.

Link to Chapter 7.


In order to solve problems, mathematicians often change their forms to ones they find easier to analyze. Such is the case in trying to find the minimum number of colors necessary to color a plane map.

Definition. Let G be a plane map. The dual graph G' is obtained from G as follows: place a node inside the interior of each region of the map. Draw an edge between nodes if they lie in adjacent regions.

In the following example, the map G is colored blue, green, and yellow, while the dual graph G' is in red (Figure 7c.1).

Image

Figure 7c.1.

It is easy to see that a planar map leads to a planar graph (without loops), and vice versa. The problem of coloring the regions in G so that no two adjacent regions have the same color is equivalent to the problem of coloring the nodes of G' so that no two adjacent nodes have the same color. In the example above, a coloring with three colors is shown.

Trials have shown simple examples of planar graphs that require four colors. For example, K4 has every node adjacent to every other so four colors are required. Moreover, since the Schlegel diagram of the tetrahedron represents K4 (Figure 7c.2a), it is clearly planar. A dual map requiring four colors might be as in Figure 7c.2b.

Image

Image

Figure 7c.2. a and b.

While many people have drawn planar maps that appeared to need five or six colors, it has always been possible to re-assign the colors to get by with four colors.

Again, in trying to prove a theorem, it is often instructive to prove a simpler theorem first. In this chapter, we shall first prove that six colors are enough, then five, and finally we will discuss the proof that four colors are enough. Since the dual of a plane map is a planar graph without loops, we shall assume throughout the rest of this chapter that the words "planar graph" refer to a graph without loops.

We start with an elementary fact that can be deduced from Corollary 5c.1 to Euler's formula (Theorem 5c.1).

Lemma 7c.1. Every planar graph has a node of degree 5 or less.

Proof. Suppose G were a planar graph with each node of degree at least 6. Then, since the sum of the degrees of the nodes is twice the number of edges, we would have 6v ≤ 2e or 3v ≤ 3. However, by Corollary 5c.1 to Euler's formula the following inequality holds: e ≤ 3v - 6. This yields the contradiction 3≤ 3v - 6.


Theorem 7c.2. Six-color Theorem. Every planar graph can be colored with no more than six colors so that adjacent nodes have different colors. (If G is planar, χ(G) ≤ 6.)


Proof. The proof is by mathematical induction on the number of nodes in G. The Theorem is clearly true for all graphs with six or fewer nodes, since each node can have its own color. Now suppose the Theorem is true for all graphs with fewer than n nodes, and let G be a graph with n nodes. Pick a node v of G of degree 5 or less (this is possible by the lemma). Color v with a color different from those assigned to its adjacent vertices in a 6-coloring of G - {v}; this assignment gives a 6-coloring of G.


Next, we hope to modify the proof of this theorem to show any planar graph can be colored with only five colors. This modification will clearly be more difficult, since there will not be a color to spare for v, necessarily. We shall have to modify the coloring of G - {v}.

Theorem 7c.3. Five-color Theorem. Every planar graph can be colored with no more than five colors so that adjacent nodes have different colors.

Proof: The proof again proceeds by induction on the number of nodes in G. This time the theorem is clearly true for all graphs with five or fewer nodes, since again each node can have its own color.

Now suppose the theorem is true for all graphs with fewer than n nodes, and let G be a graph with n nodes. As before, pick a node v of G of degree 5 or less.

  1. If deg (v)<5, look at a 5-coloring of G - {v}, and color v with a color different from that of any of its (four or fewer) adjacent nodes.
  2. Suppose deg (v) = 5, but in a 5-coloring of G - {v}, no more than four different colors are used on the five nodes adjacent to v. Then again, v may be given a fifth color.
  3. The difficulty arises when deg (v) = 5, and a 5-coloring of G - {v} colors the five nodes v1, v2, v3, v4, v5 adjacent to v with five different colors 1, 2, 3, 4, 5 as illustrated below (Figure 7c.3).

Image

Figure 7c.3.

Portions of G - {v} must be re-colored so that {v1, v2, v3, v4, v5} uses only four colors.

Consider the bipartite subgraph H1,3 of G consisting of those nodes of G colored with colors 1 and 3 and those edges of G that join a node of color 1 with a node of color 3.

Case 1 Suppose v1 and v3 are in different components of H1,3. Then interchange the colorings of the component of H1,3 containing v3 (i.e. color those that had color 1 with color 3 and vice-versa). Now v3 has color 1, and color 3 is available for v.

Case 2 Suppose v1 and v3 are in the same component of H1,3; hence there is a path from v1 to v3 in which the nodes alternate colors (dotted line in diagram below). Adding the edges v1v and vv3 completes a circuit, as indicated below (Figure 7c.4)

Image

Figure 7c.4.

Once again, the Jordan Curve Theorem comes into play. Consider the bipartite subgraph H2,4 of G defined analogously to H1,3. Since v2 lies inside the circuit and v4 outside it, there can be no path from v2 to v4 lying entirely in H2,4 (since G is planar, any path from v2 to v4 must include v or a node colored 1 or 3).

Now the component of H2,4 that contains v4 (and hence not v2) can have its colors interchanged, as happened in case 1 to a component of H1,3. This interchange gives v4 color 2, allowing v to be given color 4.

One might notice that things became more difficult as we progressed from six colors to five colors. As might therefore be expected, the situation is much more complex for four colors.

Many people believe they have proved the four-color theorem when they discover for themselves, again using the Jordan Curve Theorem, a result first proved by Augustus DeMorgan.

Theorem 7c.4. DeMorgan's Theorem. No five regions in the plane can be mutually adjacent.

This fact does not suffice to prove the four-color theorem, however. For example, we can find a map in which no more than three regions are mutually adjacent but that nonetheless needs four colors (Figure 7c.5).

Image

Figure 7c.5.

In the nineteenth century, Kempe knew the basic ideas that led to the proof of the four-color theorem in the late twentieth century. However, the details were far too complicated to pursue.

What Kempe sought was called an unavoidable set of reducible configurations. That is, he supposed that a map requiring 5 colors existed. By various arguments, he hoped to show that this map must contain one of a number of smaller submaps, a so-called unavoidable set. If he could then show each of these submaps could be colored with one fewer color (hence reducible), then this map requiring five colors could not exist.

Unfortunately, the number of configurations in an unavoidable set turned out to be very large, and showing even one was reducible could be tedious. Even using a method of Heesch called discharging, the prospects were daunting.

Eventually, Kenneth Appel and Wolfgang Haken, working at the University of Illinois, were able to devise a computer program to help analyze reducible configurations. It took 1000 hours of computer time on an IBM 360 computer to analyze an unavoidable set of 1500 configurations. This was one of the first theorems to rely on computer methods; since others rarely had the computer time or expertise to check the results, it was some time before the mathematical community came to accept this new type of proof. But they have, and hence we now have the following theorem.

Theorem 7.5. The Four-Color Theorem (Appel and Haken, 1976). Every planar graph can be colored with four (or fewer) colors so that no two adjacent nodes have the same color.