American Scientist

Four Colors Suffice: How the Map Problem Was Solved. Robin Wilson. xiv + 262 pp. Princeton University Press. First published by Penguin Books in 2002. $24.95

Progress in mathematics is inevitable: Given enough time, even the most fearsome problem surrenders to some new attack. The fall of Fermat's Last Theorem to Andrew Wiles in the mid-1990s, after battles spanning three and a half centuries, is an example. A less well-known instance is Kenneth Appel and Wolfgang Haken's conquest in 1976 of the Four-Color Problem, the subject of this lively and captivating book by mathematician Robin Wilson.

"A student of mine asked me today to give him a reason for a fact which I did not know was a fact—and do not yet," wrote the English mathematician Augustus De Morgan in 1852 to his Irish friend and colleague Sir William Rowan Hamilton. The "fact" is that only four colors are required to color any map in such a way that adjacent regions receive different colors. The student was Frederick Guthrie, but it was Frederick's older brother, Francis, who first proposed it. Francis decided that it must be true after coloring a map of the counties in England, and he allowed Frederick to submit the challenge to De Morgan. "What do you say?" continued De Morgan in his letter to Hamilton. "The more I think of it the more evident it seems."

Hamilton, noted for his discovery of quaternion algebra, was uncharacteristically laconic in his reply, saying only, "I am not likely to attempt your 'quaternion' of colours very soon." Perhaps he sensed that the Four-Color Problem was a dangerous animal that would devour all who came near. De Morgan managed not to fall prey (he died of natural causes in 1871), but in 1860 he did write about the Four-Color Problem in, of all places, a book review. This strengthened the beast, which soon swam across the Atlantic Ocean and fed on American mathematicians.

Back in England, at a meeting of the London Mathematical Society in 1878, the prolific mathematician and successful barrister Arthur Cayley, who had apparently read De Morgan's review, raised a query about the map problem, thereby attracting its next victim, Alfred Bray Kempe. Kempe, who had been Cayley's student at Cambridge, practiced law after graduating, while maintaining his mathematical interests. He wrote a popular book on linkages with the wonderful title How to Draw a Straight Line. However, he owed his fame to the erroneous proof of the Four-Color Problem that he published in 1879 in volume 2 of the American Journal of Mathematics.

Kempe had come up with his "proof" in response to Cayley's 1878 inquiry. It was considered correct for 11 years, until Percy John Heawood, a mathematician and classical scholar at Durham Colleges, discovered its fatal flaw. Heawood couldn't right Kempe's capsized vessel, but he was able to salvage something of value from its hold: He produced a (correct) proof of the five-color version of the problem, the statement of which can be safely left to the reader.

Earlier books, such as The Four-Color Problem, by Oystein Ore (Academic Press, 1967), and The Four-Color Problem: Assaults and Conquest, by Thomas L. Saaty and Paul C. Kainen (McGraw-Hill, 1977), relate some of the relevant history in their introductions, but they are primarily technical. In contrast, Four Colors Suffice is a blend of history, anecdotes and mathematics. Mathematical arguments are presented in a clear, colloquial style, which flows gracefully.

Because the subtitle, How the Map Problem Was Solved, gives away the ending to this mystery, I feel at liberty to tell you: The computer did it. Appel and Haken reduced the proof to a check of 1,936 special cases, which required 1,200 computer hours. The proof depended on electricity and experimentation. In the final chapter of Four Colors Suffice, Wilson surveys the skeptical reactions of the mathematics community to the use of this strategy. Many contended that a proof should come from human understanding, not a mechanized bludgeon. Some wondered if the nature of mathematical proof had changed forever. The debate continues today.

My only complaint about the book is that its final section is too brief and omits mention of alternative reformulations of the map problem. For example, Louis Kauffman showed in 1990 that the problem is equivalent to an astonishingly simple question about quaternions. Had the reluctant Hamilton known this in 1852, the history presented here might have been quite different.

The quaternion formulation is mentioned in Kauffman's 31-page article "Reformulating the Map," very readable and freely available on the Web at www.math.uic.edu/~kauffman/RM.pdf. There Kauffman explores the approach of George Spencer-Brown, an iconoclast whose work is dismissed in Four Colors Suffice.

Wilson insists that a solution that runs along the lines of the Appel-Haken proof but doesn't use a computer "is almost certainly unattainable." Yet the hope remains that one day some reformulation will lead to a new, more satisfying proof of the Four-Color Theorem. The progress of mathematics is, after all, inevitable.—Daniel S. Silver, Mathematics, University of South Alabama, Mobile