Four Colors Suffice: How the Map Problem Was Solved

Robin Wilson can write. Of course, we've known that for a long time, from his many previous works (sometimes coauthored): thirteen books (by my last count) on graph theory and combinatorics; four volumes on Gilbert and Sullivan; four on the history of mathematics; one on mathematical stamps; and now a book telling the story of the solution of the four color problem.

In writing it always helps to have a topic that is by its very nature an entertaining tale with a large and colorful cast of characters. In the author's own words, taken from the preface, we are told that this cast includes: "Lewis Carroll, the Bishop of London, a professor of French literature, an April Fool hoaxer, a botanist who loved heather, a mathematician with a passion for golf, a man who set his watch just once a year, a bridegroom who spent his honeymoon colouring maps, and a Californian traffic cop."

Now let's take a look at the problem: Can every map be colored with at most four colors in such a way that neighboring countries are colored differently? The author explains, for his nonmathematical audience, that a proof that four colors suffice must show that all maps can be colored with four colors only. Showing that millions or billions of maps can be colored with four colors will not do.

In the statement of the problem there are some assumptions. For one thing, we assume that the map is in the plane (or on a sphere — the same problem, as one can see from a stereographic projection).

An interesting question arises in looking at the map of the United States: Utah, Colorado, New Mexico, and Arizona come together at one point, the famous "four corners". We adopt the convention that opposite states across such a point can be colored the same color, that is, Utah and New Mexico can share the same color, or Arizona and Colorado can. If this convention were not adopted, then slices of a pie, all meeting at a point in the center of a pie, could force the number of colors to be arbitrarily large since they all meet at a point.

Now, the map of the United States, for example, shows that Nevada borders on five states, Arizona, California, Oregon, Idaho, and Utah. The ring of states around Nevada cannot be colored with two colors (two adjacent states would have to be the same color), so it takes three colors to color this ring of states. But Nevada borders on every state in the ring, hence a fourth color is necessary. Three colors will therefore not suffice.

The analogous problem for the torus is not difficult: every map on a torus can be colored with seven colors and there are such maps that require seven colors. The Heawood conjecture of 1890 gives the exact number of colors required to color maps on an h-holed torus. The proof of this conjecture was provided by Gerhard Ringel and Ted Youngs in 1968 and accounts for the reference in the preface to the traffic cop in California.

So how did people become interested in the coloring of maps? At this point we should note that the problem is apparently of no interest to cartographers. They don't seem to care whether the minimum number of colors is four or five or... It's also true that cartographers have other problems to worry about, for example, what happens when you want to keep the same color for all bodies of water (blue) or for the noncontiguous regions all belonging to the same empire. There was a time when on maps of the world much of the land mass looked pink — all of the pink regions were parts of the British Empire. These cases are extensions of the original problem and the present work only mentions them in passing.

If the four color problem is not of interest to cartographers, are there other applications? Yes, the time spent on the problem, if justification were needed, made other applications possible. The search for a proof motivated many results in graph theory and elsewhere in mathematics, ideas now useful in other contexts.

The original problem seems to have arisen as a children's game. In 1852 Augustus De Morgan at University College, London, wrote to Sir William Rowan Hamilton, the Irish Astronomer Royal, and said that a student of his asked him "to give him a reason for a fact which [he] did not know was a fact — and do not yet," why four colors seemed to be sufficient to color any map in the plane. He gave a figure to show that three would not suffice but could not come up with a map that required five colors. De Morgan's student, Frederick Guthrie, was not actually the one who discovered this while coloring a map of the counties of England. It was Guthrie's brother Francis, who later became a professor of mathematics at the South African University, Cape Town. From there interest in the problem spread and the list of contributors included, in England, Arthur Cayley, Alfred Bray Kempe (who claimed to have a proof, later demolished by Heawood, as we shall see), and Peter Guthrie Tait, then in the United States, Benjamin Peirce, Charles Sanders Peirce, and many others. Hermann Minkowski heard of the problem, and thinking that he could polish it off in a topology class at Göttingen, he proceeded to outline a proof. It, like so many others, turned out to be defective. In the first half of the twentieth century, those working on it most assiduously were Americans: G. D. Birkhoff, Oswald Veblen, Philip Franklin, Hassler Whitney, among others. It was Birkhoff's contribution that led to the mention in the preface of coloring maps on a honeymoon. Arthur Bernhart at Oklahoma completed Birkhoff's work on maps with rings of six countries. Shortly after Bernhart was married his wife saw Mrs. G. D. Birkhoff at a meeting and asked her, "Did your husband make you draw maps for him to color on your honeymoon, as mine did?" Garrett Birkhoff, G. D. Birkhoff's son, when asked about the story said he thought it is probably apocryphal.

G. D. Birkhoff, we are told, once remarked that almost every great mathematician had worked on the four-color problem at one time or another. We assume he referred to all great mathematicians who lived beyond a certain date. Birkhoff thought that he could solve the problem by investigating the properties of chromatic polynomials. But his work in that direction did not pay off. It turns out that some of his contributions to the problem were anticipated by the French poet, Paul Valéry, who, though he did not publish the work, recorded it in his diaries.

To many readers this history will be familiar, at least in broad outline, but Wilson provides a lively narrative and good, easy-to-read arguments showing not only some of the victories but the defeats as well.

Some early "proofs" were accepted for years before being exposed as incorrect. Kempe's "proof" appeared in the American Journal of Mathematics in 1879, with simplified forms appearing the following year in the Proceedings of the London Mathematical Society and in Nature, all highly respected journals. However Percy John Heawood at Durham College published an article in 1890 in the Quarterly Journal of Mathematics pointing out a fundamental error in Kempe's eleven-year old paper. Heawood, incidentally, was the mathematician mentioned in the preface, the one who set his watch once a year on Christmas Day, even though the watch was consistently slow. He once remarked when asked the time: "No, it's not two hours fast; it's ten hours slow!" One of his other eccentricities was his enjoyment of committee meetings. He "considered a day as wasted if he did not attend at least one committee." To give the reader a taste of Wilson's deft prose, here's a passage describing the discovery of the flaw in Kempe's proof: "[His] proof of the four-colour theorem was a very good one. It was incorrect, but it was a very good incorrect proof. Not only did it convince Victorian mathematicians for eleven years, but most of the ideas it contained were sound and would form the basis for later assaults on the problem, including the one that was ultimately to prove successful."

Excitement really began to build up in the early 1970s when Heinrich Heesch and Wolfgang Haken (joined later by the gifted computer expert, Kenneth Appel) began an all-out assault on the problem using a computer to check complex sub-problems. By 1976 an announcement of the solution appeared in The Times of London. This coincided with a new postmark for the Department of Mathematics at the University of Illinois at Urbana-Champaign, the home campus of Haken and Appel. This postmark read: "Four Colors Suffice," and provided the title for the Wilson book. The New York Times held back on coverage of the result: they had a policy of not covering "proofs" of the four color problem "because they were all false anyway." Haken gave a talk on the solution at the joint meetings of the Mathematical Association of America and the American Mathematical Society in Toronto. It was greeted with skepticism. Many mathematicians did not regard something as a proof when it required so much work be done on a computer. And it raised difficult philosophical questions about what a mathematical proof really is. If the computer component makes it less a proof because humans cannot get in there and check every step themselves, then what other proofs — the classification of the simple groups, for example — might not qualify as proofs just because of their excessive length? With some of these proofs there wouldn't be enough time in the readers' lifetimes to check every single detail. Many readers will remember the paper of Thomas Tymoczko in the Journal of Philosophy, questioning whether the Haken-Appel "proof" was really a proof.

There's no room here to get involved in the details of the Haken-Appel argument or the storm it caused among some mathematicians and philosophers. People will just have to read the details in the book. In some ways the Haken-Appel story and what has followed since make up the most gripping part of the tale. And it is good to see the details of where things stand now, over twenty-five years after the announcement, in a form that a non-specialist can understand. The latter half of this book is a real page turner as Haken and Appel race to reduce the list of reducible configurations to be checked from 1936 to 1482 to 1405. There was pressure on them too from Allaire in Canada, and from Heesch, Dürre, Shimamoto and others from Chicago who were zeroing in on the solution using somewhat similar techniques. Even those with only a mild interest in coloring problems or graphs or topology will have fun reading this book.

One can always find something one might have done otherwise. The designers have set long quotes in serif type and the main text in a rather large sans serif. That along with the fact that lines are not right justified gives the pages a rather strange look. It's a minor matter. There's some evidence of a dispute over spellings between author and publisher. On the cover the spelling "color" is used, as it is on the title page. But by the time one reaches the table of contents the word is consistently spelled "colour." The author, though, British, has close American ties, having taught and lectured extensively in the United States. His Ph.D. is from the University of Pennsylvania. I have not found errors, other than the one caught by the reviewer for the New York Review of Books: Lipman Bers comes out Lipton Bers. It's scarcely a fatal flaw. There are ample references, a very helpful chronology of events, and a glossary of technical terms, should one's memory on occasion fail.

The text is consistent — it's entertaining, erudite and loaded with anecdotes, playful uses of language, and, just to top it off, there are three charming quotes just prior to the table of contents — from A. E. Housman, Mark Twain, and Tom Robbins. Here's the quote from Mark Twain's Tom Sawyer Abroad: "Suppose there's a brown calf and a big brown dog, and an artist is making a picture of them... He has got to paint them so you can tell them apart the minute you look at them, hain't he? Of course. Well then, do you want him to go and paint both of them brown? Certainly you don't. He paints one of them blue, and then you can't make no mistake. It's just the same with maps. That's why they make every state a different color... "

Gerald L. Alexanderson (galexand@math.scu.edu) is Valeriote Professor of Science at Santa Clara University. He has served as Secretary and President of the MAA.