The Four-Color Map Problem

      When I was around a dozen years old I became enamored of the four-color map problem. I'm not sure how I discovered it: I remember a science-fiction story in which the problem was described. As I recall, the story's narrator discovers a solution that he then could no longer remember.

      But the idea was appealing. There were some rules to the game, of course: The map must include only self-contained, contiguous areas such as Kansas or Idaho. It could not include jurisdictions that have one government but two locations, such as Michigan, with its upper peninsula, or Germany during the time of the Polish Corridor. One government in two places requires that both parts be the same color, which limits the colors available for the areas touching them. Countries that came together in a point also did not count, such as the situation of Colorado, Utah, New Mexico, and Arizona. It is possible to go to Four Corners and put one hand or foot in each of the states, but on a map two diagonally opposed states could be the same color. (When visiting Four Corners once I spread-eagled myself across all four states and wondered briefly where I would vote if I lived on that spot. The answer, I realized immediately, was "Nowhere": Four Corners is in the middle of an Indian reservation, and thus the residents are not able to vote in any state.)

E. C. Bridgman's, 1896 Rail Road and Township map of New York illustrates the four color mapping problem - as a practical matter, green, yellow, pink and tan are sufficient to map the townships. Some say the four color theorum was finally proved by Appel and Haken in 1976, but others claim that the question is yet to be resolved satisfactorily. Map from The Library of Congress Geography and Map Division

      Yet at the time of my childhood the four-color map theorem had never been proved, and in fact could have been disproved by creating a map that required five colors.

      Since I had already disproved the existence of Santa Claus and the doctrine of adult infallibility, this simple challenge seemed easily overcome. So it happened that, in spite of having virtually no mathematical knowledge, I set out to draw a map that required at least five colors. My bedroom and desk became littered with scraps of paper on which I had drawn various patterns, using four directions of hatching or various colored pencils to identify each of the sections. It seemed so simple to draw a map that needs five colors: Why couldn't it be done?

      The answer is, of course, is "Because it's mathematically impossible."

      This impossibility was not always obvious. The four-color map problem remained unresolved for more than a century and was not conclusively proved until 1976. Even then the proof seems questionable to some authorities because it was so complex that its calculation required a computer.

      The four-color map problem was first proposed in 1852 by Francis Guthrie, a mathematician who was engaged in drawing a map of the counties of Britain. Guthrie noticed that he could make every county a different color from the those touching it, but only needed four colors to do so. Try as he might, he couldn't prove why this was so. Guthrie mentioned this discovery to his brother, who mentioned it to another mathematician, Augustus de Morgan, who mentioned it to other mathematicians, and eventually one Arthur Cayley presented the problem to the London Mathematical Society in 1878. The response was swift: A year later Arthur Bray Kempe published a proof of the theorem. But haste breeds error, and in 1890 Percy John Heawood pointed out the fatal flaw in Kempe's proof.

      The four-color map issue remained unresolved until 1976, when, aided by a computer, Kenneth Appel and Wolfgang Haken analyzed 1476 configurations (the minimum reducible number) and determined that none of the possible arrangements required more than four colors. Additional work since then has ensured that the matter is thoroughly settled. There is no "five-color map"; my childhood efforts to draw a five-color map were, as I realized even back then, doomed from the start.

      Although in theory a map of contiguous territories only requires four colors, in practice maps often use more. A limit of four colors only allows the cartographer to differentiate among the various jurisdictions or regions, and does not provide any additional dimensions of information. Using a wider range of colors or tones a mapmaker might identify individual states while also providing information about which states produce the most soybeans, which supported the North during the Civil War, or the order in which each state's government was established. Aesthetics might also suggest using more than four colors on any individual map. But for the fundamental purpose of showing regional borders, four colors are all you need.