Multicolored Maps

Maps of the United States often show the states in different colors. In general, mapmakers use enough colors to make sure states that touch are never the same color.


Suppose you have only three colors of pens. Is that enough to fill in all the states? Not quite. Nevada, for example, is surrounded by five other states: California, Oregon, Idaho, Utah, and Arizona. There's no way to color this group of states without using a fourth color. Can you figure out what other states force the use of a fourth color?

Would you ever need five colors? In 1976, two mathematics professors at the University of Illinois proved that four colors would be enough for any map that could be drawn on a flat piece of paper.

Curiously, four colors are needed whenever a state is surrounded by three or more states and the number of surrounding states is an odd number. You see that not only in a U.S. map but also in a map of South America. The country Bolivia, for example, is surrounded by an odd number of countries: Peru, Brazil, Paraguay, Argentina, and Chile. What other country in South America is in the same situation?


Simpler maps sometimes use fewer than four colors. For example, if you had a map that looked like a checkerboard or some other sort of grid, you would need only two colors.

What about a pattern made up of tiles shaped like kites and darts or a pattern made of diamonds like the one below?


Mathematicians have recently proved that you need at most three colors for such a map.

---

Muse, February 2002, p. 44.

Answer to U.S. map: Kentucky, which is surrounded by seven states; and West Virginia, which is surrounded by five states.

Answer to South American map: Paraguay, which is surrounded by three countries.