10 Pages

The Mathematics of Map Coloring

Looking at a colored map of the United States in almost any atlas, we see that neighboring states are distinguished by being differently colored, and the total number of colors used is five or six. Apparently the artist did not realize that four colors would have sufficed. (It is understood that two states may be colored alike if they merely have a point in common, as in the case of Arizona and Colorado.) The map-coloring problem becomes slightly more complicated if we include seas and lakes and insist on making them all blue. For instance, we need three different colors (say green, red, and yellow) for Belgium, France, and Germany, which all touch one another; Holland may have the same color as France, but Luxembourg must be blue, like the sea, if no fifth color is available. With this slight departure from practical cartography, we now formulate the mathematical question: