A century and a half ago, a student who was coloring a map of England noticed that he only needed four colors to do the job—that is, to ensure that no counties sharing a border, such as Kent and Sussex, got the same color. This led him to guess that four colors might be sufficient for any map, real or invented. He mentioned this idle surmise to his brother. His brother in turn mentioned it to a distinguished mathematician, who, after a little experimentation to see if it looked plausible, tried and failed to prove that it was true.
In the decades that followed, many other mathematicians, along with innumerable amateurs—including a great French poet, a founder of American pragmatism, and at least one bishop of London—were similarly engrossed and confounded by the map problem. So easy to state that a child can understand it, the “four-color conjecture” came to rival Fermat’s last theorem as the most famous conundrum in all mathematics. Finally, in 1976, the world received the news that the conjecture had been resolved. When it became clear how this was accomplished, however, the celebratory mood gave way to disappointment, skepticism, and outright rejection. What had been a problem in pure mathematics evolved into a philosophical question, or rather a pair of them: How do we justify our claims to mathematical knowledge? And can machine intelligence help us grasp a priori truths?
For all of its mathematical and philosophical interest, the map problem has no obvious practical importance—at least not for map-makers, who show no tendency to minimize the number of colors they use. Still, it is instructive to approach the matter by way of a glance at an actual atlas. Turn to a map of Europe, and look at the part consisting of Belgium, France, Germany, and Luxembourg. Each of these countries shares a border with the other three, so it is pretty obvious that they cannot be distinguished with fewer than four colors. You might think that four colors would be needed only when a map contains a quartet of mutually neighboring regions like this. If you do, turn to a map of the United States, and look at Nevada along with the five states that ring it (California, Oregon, Idaho, Utah, and Arizona). No four of these states are mutually neighboring, the way Belgium, France, Germany, and Luxembourg are. Yet the cluster as a whole cannot be distinguished with fewer than four colors, as you can easily verify. On the other hand—and this may shake your intuition a bit—Montana and the six states that ring it can be distinguished with a mere three colors.
Some maps need four colors: that much is patent. What the four-color conjecture asserts is that there is no possible map that needs more than four colors. What would it mean to “resolve” this conjecture? There are two possibilities. Suppose—as some mathematicians have believed—the conjecture is false. Then drawing just one map …