Discrete Mathematics: Elementary and Beyond

13.4 Map Coloring and the Four Color Theorem 205

FIGURE 13.7. Four mutually neighboring countries

boundary, and so all four need different colors in a “good” coloring (see
Figure 13.7).
Now consider a “real-life” planar map, for instance the map of the states
of the continental US. We assume that each country (state) is connected
(consists of one piece). In school maps usually six colors are used, but four
colors are enough, as shown in Figure 13.8.

FIGURE 13.8. Coloring the states of the United States.

Would three colors be enough? One can easily see that the answer is
negative. Let’s start to color our map with three colors, say red, blue, and
yellow (it does not make any difference which of the three colors we start
with); we have to prove that sooner or later we get stuck. Let’s start by
coloring Nevada red. Then all the neighboring states can get only colors
blue or yellow. Let’s color California blue (without loss of generality). Then
the next neighboring state clockwise, Oregon, is a common neighbor of both
Nevada and California, so it must be colored yellow; the next state, Idaho,
must be blue again; the next state, Utah, must be yellow. But now we
are stuck, because the last state among the neighbors of Nevada, Arizona,