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 that required five or more colors would clinch the matter. (In the Scientific American of April 1975, Martin Gardner published a complicated map, consisting of 112 regions, that he claimed could not be colored with fewer than five colors. Hundreds of readers sent in copies of the map that they had laboriously colored with just four colors, perhaps not realizing that Gardner was enjoying a little April Fools’ joke.) To establish that the four-color conjecture is true, by contrast, one would have to show that every conceivable map, of which there are infinitely many, could be colored with only four colors, no matter how numerous and convoluted and gerrymandered its regions might be.
So the simplicity of the four-color conjecture is deceptive. Just how deceptive is made clear by Robin Wilson’s delightful history of the quest to resolve it, much of which reads like a comedy of errors. Francis Guthrie, the student in London who in 1852 first guessed that four colors sufficed, apparently imagined he had proved the conjecture as well. Although Guthrie later became a professor of mathematics in South Africa, he never published anything on the map problem, preferring, it seems, to indulge his interest in botany (a species of heather is named after him). He did, however, discuss it with his younger brother, Frederick, who brought it to the attention of Augustus De Morgan, his mathematics professor. De Morgan was a pretty good mathematician and an important figure in the development of logic. Intrigued by the four-color problem, he grew obsessed with the idea that if a map contained four mutually neighboring regions, one of them must be completely enclosed by the other three (as, to revert to an earlier example, Luxembourg is completely enclosed by Belgium, France, and Germany). He believed, quite wrongly, that this “latent axiom” was the key to proving the conjecture, which he continued to vex over until his death in 1871.
It was De Morgan who first mentioned the four-color conjecture in print—in, of all places, an unsigned philosophy review he contributed in 1860 to a popular literary journal, the Athenaeum. Word of it crossed the Atlantic to the United States, where the philosopher C.S. Peirce fell under its spell. Peirce pronounced it “a reproach to logic and to mathematics that no proof had been found of a proposition so simple,” and he presented his own would-be proof to a mathematical society at Harvard in the late 1860s. No record of it survives. Later, however, Peirce had to acknowledge another man’s breakthrough, which he helped to publicize in a notice that appeared in The Nation on Christmas Day of 1879. In doing so, Peirce unwittingly ratified what would become the most famous fallacious proof in the history of mathematics.
Here is perhaps a good place to say something about how mathematicians go about proving propositions—especially those, like the four-color conjecture, that encompass an infinite number of cases. One approach is the method of mathematical induction. This is sometimes likened to knocking down an endless row of dominoes. The crucial step in mathematical induction is showing that if such-and-such is true for the number n, then it is also true for n+1. In the domino simile, that means each falling domino knocks down its immediate successor, ensuring that all of them ultimately fall. To apply mathematical induction to the map problem, one would have to show that if any map having n regions can be colored with four colors, then so can any map having n+1 regions. That turns out to be extremely tricky to do. When you add the (n+1)th region to a given map, you might have to recolor some or all of the n other regions to make the new one fit in the four-color scheme. No one has ever been able to find a general recipe for such a recoloration. So much for the falling-dominoes approach.
Happily, there is another strategy for proving a proposition of infinite scope: proof by contradiction. You take the denial of what you want to establish and show that it leads to absurdity. In the case of the four-color conjecture, this means you pretend that there exist counterexamples to the conjecture—maps that need five or more colors—and then derive a contradiction from that assumption. Since such counterexamples would violate the four-color principle, they are colloquially called “criminals.” Criminal maps, if they existed, could contain any number of regions, but it is useful to focus on those having the absolute smallest number. These are called minimal criminals. (Obviously, a minimal criminal would have to have at least five regions to need five colors.) Any map with fewer regions than a minimal criminal is bound, by definition, to be law-abiding—that is, four-colorable.
Now we are in an interesting position. Suppose you take a minimal criminal, pick one of its regions, and shrink that region down to a point. The resulting map, containing as it does one fewer region, must be law-abiding. Therefore it can be colored with four colors. So color it. Now restore the shrunken region by blowing it up again. If you picked that region wisely, then there might be a way of incorporating it into the new four-color scheme. If, for instance, the region you picked had a border with only three other regions, then you are in luck: when you restore it under the new four-color regime, there will be a color left over for this region that distinguishes it from its three neighbors. But now you have managed to color the original map with four colors. So the supposed minimal criminal was not criminal after all!
Clearly, no map that aspires to be a minimal criminal can contain a region that borders only three other regions. If every map contained some such “reducible configuration,” then no map could be a minimal criminal. But no minimal criminals means no criminals, period. (If criminal maps exist at all, some must rank lowest in number of regions.) And no criminals means that every map must be law-abiding—that is, four-colorable.
It was by precisely such logic that Alfred Bray Kempe, a London barrister and amateur mathematician, claimed in 1879 to have proved the four-color conjecture. Kempe’s reasoning was replete with mathematical complications, but it appeared persuasive, and not just to C.S. Peirce. Leading mathematicians in Britain, on the Continent, and in the United States agreed that it was the long-sought solution to the map problem. Kempe was made a fellow of the Royal Society and eventually knighted. His “proof” stood for a decade, until a subtle but fatal flaw was found. The man who detected this flaw was a classicist and mathematician called Percy Heawood—or “Pussy” Heawood by his friends, owing to his cat-like whiskers.
Heawood, who was almost apologetic about overturning the result, had personal oddities that make him stand out even in this eccentric-filled saga. A meager, slightly stooping man, he was usually clad in a strangely patterned Inverness cape and he carried an ancient handbag. His habitual companion was a dog, who accompanied him to his lectures. He had “a passion for committees and considered a day as wasted if he did not attend at least one committee meeting,” Wilson tells us. He set his slow-running watch just once a year, on Christmas Day, and then did the necessary calculations in his head when he needed to know the time. “No, it’s not two hours fast,” he once insisted to a colleague, “it’s ten hours slow!” But he was not without practical talents: when the eleventh-century Durham Cas- tle was on the verge of sliding down the cliff on which it was built into the River Wear, Heawood almost single- handedly raised the funds to save it.
Four Colors Suffice is strewn with good anecdotes, and the author, a fellow of Keble College, Oxford, also proves himself skillful at making the mathematics accessible. For many readers, I suspect, the intellectual climax of the book will come when they are treated to an elegant proof of the “six-color theorem.” This is like the four-color conjecture but obviously weaker: it says that six colors are enough to color any possible map in such a way that neighboring regions are colored differently. The six-color theorem is worth considering because it reveals the mathematical roots of the map problem, which extend back to the mid-eighteenth century and the great Swiss mathematician Leonhard Euler (whose name, Wilson considerately tells us, is pronounced “oiler”; when I was an undergraduate math student, we were told to think of the Houston Eulers). Euler was perhaps the most prolific mathematician in history. Among the discoveries he made, while shuttling between the courts of Frederick the Great and Catherine the Great, was the formula V–E+F=2, which was not long ago voted the second-most-beautiful theorem in mathematics.1 Euler’s formula holds for any polyhedron—that is, for any solid bounded by plane surfaces, such as a cube or a pyramid. It says that if you count up the polyhedron’s vertices (V), subtract the number of edges (E), and then add the number of faces (F), the result is always 2. A cube, for instance, has 8 vertices, 12 edges, and 6 faces. And sure enough, 8–12+6=2.
What do polyhedra have to do with maps? Well, if you take a polyhedron and (after a little surgery) flatten it out, each face looks like a region of a map. Conversely, you can take a map and knit it up into a polyhedron. The sizes and shapes of the regions will get altered in the process, but that does not affect the overall configuration of the map or the number of colors it needs. The four-color conjecture is thus a problem of topology, the branch of mathematics that is concerned with properties that are not altered by twisting and stretching.
Suppose you apply Euler’s formula to a map. F becomes the number of regions, E the number of borders, and V the number of points at which borders intersect. Then you can derive a result that is crucial to the map problem: every map must have at least one region with five or fewer immediate neighbors. This is agreeably easy to prove. If there were some map in which every region had at least six neighbors, then, by counting up the regions, borders, and points, and plugging them into Euler’s formula, you’d get the extraordinary result that 0=2. Contradiction! So some region in every map is guaranteed to border on five or fewer other regions.
With this result in hand, it is the work of a moment to prove the six-color theorem. Suppose there were criminal maps that needed seven or more colors. Take a minimal criminal. Since it must have at least one region with five or fewer neighbors, pick that region and shrink it to a point. Color the reduced map, which must be law-abiding, with six colors. Now reinstate the shrunken region. Since it has five or fewer neighbors, there must be a spare color for it among the six available colors. This contradicts the assumption that the map was a minimal criminal, establishing the six-color theorem.
The logic behind all this is lucidly laid out by Wilson. You can hold it in your mind and “see” why the six-color theorem has to be true. The proof is surprising and inevitable at the same time; it’s almost witty. Alas, that is as good as the map problem gets, aesthetically speaking. The method that Kempe used in 1879 to get the six-color minimum down to the desired four was tortuous; it drew on no deep mathematical ideas; and it contained a fallacious step to boot. Still, when Heawood detected its flaw, he was able to salvage enough of the argument to show that every map could be colored with five or fewer colors. (The proof is given by Wilson, though the details are tedious to follow.)
Others attracted to the four-color conjecture included Frederick Temple, the Bishop of London and later Archbishop of Canterbury, who published a fallacious proof; and the French poet Paul Valéry, who left behind a dozen pages of substantial work on the problem in his 1902 diary. Some felt that the nettlesome matter would be dispatched as soon as a really first-rate mathematician turned his attention to it. The great Hermann Minkowski tried to toss off a proof during one of his lectures at the University of Göttingen; after wasting several weeks’ worth of classes pursuing it, he announced to his students, “Heaven is angered by my arrogance. My proof…is also defective.” Other leading mathematicians, perhaps wisely, gave the problem a miss. After all, it was not really in the mainstream of mathematics. Nothing important was known to hang on its truth or falsity. When David Hilbert, perhaps the paramount mathematician of his time, set out before an international conference in Paris in 1900 what he considered to be the twenty-three most significant problems in mathematics, the four-color conjecture was not among them.
Still, its notoriety and elusiveness continued to make it irresistible to mathematicians on both sides of the Atlantic (some of whom came to regret the time they devoted to it). The ongoing strategy was essentially the one Kempe used: find all the loopholes that might permit counterexamples to the four-color conjecture, and then close them. For this to work, of course, the number of loopholes must be finite; otherwise, they could not all be checked and shown closable. As the twentieth century progressed, some mathematicians found ingenious ways of producing complete sets of loopholes; others found equally ingenious ways of closing them. The problem was that these loophole sets (called “unavoidable sets”) were absurdly large, consisting of as many as ten thousand map configurations. And closing a given loophole (by showing the configuration in question to be “reducible”) could be a monumentally laborious task, one that no human mathematician would be able to carry out. By the 1960s, however, a few people working on the problem had begun to suspect that the loophole-checking process might be made sufficiently routine to be captured by a mechanical algorithm. Which raised an interesting possibility: perhaps the four-color conjecture could be proved with the help of a computer.
Mathematicians, it should be noted, were slow to warm to computers. Traditionally, from Pythagoras on, they have relied on pure hard thought to gain knowledge of new truths. It used to be said that a mathematics department was the second cheapest for a university to fund, because its members required only pencils, paper, and wastebaskets. (The cheapest would be the philosophers, because they don’t need the wastebaskets.) As late as 1986, a mathematician at Stanford boasted that his department had fewer computers than any other, including French literature. In any case, the four-color conjecture initially seemed too unwieldy even for a computer. It looked as though working through all the cases would take as long as a century on the fastest machine. But in the early 1970s, Wolfgang Haken, a mathematician at the University of Illinois, refined the methodology. Together with Kenneth Appel, a gifted programmer, he began a sort of dialogue with the computer, one aimed at reducing the number of loopholes and plugging them more efficiently. “It would work out complex strategies based on all the tricks it had been ‘taught,'” Haken later said of the machine, “and often these approaches were far more clever than those we would have tried.”
Unknown to Appel and Haken, other researchers scattered across the globe, in Ontario and Rhodesia and at Harvard, were closing in on a solution using similar methods. Meanwhile, at least one mathematician was still trying to construct an intricate map that required five colors. In June of 1976, after four years of fierce work, a thousand hours of computer time, and some crucial help from a professor of literature in Montpellier, France, Haken and Appel got their result: four colors indeed suffice. The story was broken by The Times of London that same month.2 The four-color conjecture had become the four-color theorem.
Or had it? Whatever the world at large made of this news, many mathematicians reacted sourly when they learned of the details behind it. “Admitting the computer shenanigans of Appel and Haken to the ranks of mathematics would only leave us intellectually unfulfilled,” is a typical comment quoted by Wilson. There were three distinct causes for unhappiness. The first was aesthetic. The proof was unlovely; its bulldozer-like enumeration of cases failed to woo and charm the intellect. And, as G.H. Hardy once declared, “there is no permanent place in the world for ugly mathematics.” The second reason had to do with utility. A good proof should contain novel arguments and reveal hidden structures that can be applied elsewhere in mathematics. The Haken-Appel proof seemed sterile in this respect. Nor did it provide any insight into why the four-color theorem was true. The answer just sat there like “a monstrous coincidence,” as one mathematician put it.
The third and most important reason was epistemological. Did Haken and Appel’s accomplishment really furnish grounds for claiming that we know the four-color conjecture to be true? Was it really a proof at all? Ideally, a proof is an argument that can be translated into a formal language and verified by the rules of logic. In practice, mathematicians never bother with such formal proofs, which would be cumbersome in the extreme. Instead, they make their arguments reasonably rigorous by spelling out enough of the steps to convince experts in their field. For an argument to be convincing, it must be “surveyable”; that is, it must be capable of being grasped by the human mind and checked for mistakes. And that was certainly not the case with Haken and Appel’s proof.
The human part of the argument, comprising some nine hundred pages, was daunting enough. But the in silico part, which yielded a four-foot-high computer printout, could never be humanly verified, even if all the mathematicians in the world set themselves to the task. It was as though a key stage in the reasoning had been supplied by an oracle in the form of a long sequence of “yeses.” If a single one of these “yeses” should have been a “no,” the entire proof would be worthless. How could we be sure that the computer’s program did not contain a bug? To check the Haken-Appel result, referees resorted to running a separate computer program of their own, the way a scientist might duplicate an experiment done in a different laboratory. In an influential paper published in 1979 in The Journal of Philosophy, “The Four-Color Problem and Its Philosoph-ical Significance,” the late philosopher Thomas Tymoczko argued that such computer experiments introduced an empirical element into mathematics. Almost all mathematicians now believe that the four-color theorem is true, but they do so on the basis of corrigible evidence. The theorem conspicuously fails to conform to the Platonic ideal of certain, absolute, a priori knowledge. The most we can say is that it is probably true, like the theories of physics on which the operation of the machine that helped establish the theorem are based.
The four-color breakthrough marked a shift in mathematical practice. Since then, several other conjectures have been resolved with the aid of computers (notably, in 1988, the nonexistence of a projective plane of order ten). Meanwhile, mathematicians have tidied up the Haken-Appel argument so that the computer part is much shorter, and some still hope that a traditional, elegant, and illuminating proof of the four-color theorem will someday be found. It was the desire for illumination, after all, that motivated so many to work on the problem, even to devote their lives to it, during its long history. (One mathematician had his bride color maps on their honeymoon.) Even if the four-color theorem is itself mathematically otiose, a lot of useful mathematics got created in failed attempts to prove it, and it has certainly been grist for philosophers in the last couple of decades. As for its having wider repercussions, I’m not so sure. When I looked at the map of the United States in the back of a huge dictionary that I won in a spelling bee for journalists a few years ago, I noticed with mild surprise that it was colored with precisely four colors. Sadly, though, the states of Arkansas and Louisiana, which share a border, were both blue.
May 29, 2003
The winner of the beauty contest, according to a 1988 survey published in The Mathematical Intelligencer, was eiΠ=–1. ↩
The warier New York Times waited two months to acknowledge the solution, in an Op-Ed column by the eminent Columbia mathematician Lipman Bers—not “Lipton Bers,” as the author has it. ↩