Four and no more

In October 1852, Augustus De Morgan, professor of mathematics at University College London, wrote to Sir William Rowan Hamilton in Dublin, saying: "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. He says that if a figure be anyhow divided and the compartments differently coloured so that figures with any portion of common boundary line are differently coloured - four colours may be wanted but not more."

Thus began the four-colour problem of finding a proof that every map can be coloured with just four colours. Over the next 120 years many distinguished mathematicians tried without success to solve it - indeed, a "proof" by Alfred Kempe in 1879 was completely accepted for 11 years until a fundamental error was discovered - and the four-colour problem again became one of the most celebrated problems in mathematics. Eventually, in 1976, Kenneth Appel and Wolfgang Haken cracked the problem with a brute-force approach relying heavily on the computer. This was the first major mathematical proof to rely on computer calculations, and raised several philosophical questions about the nature of a mathematical proof. Although many simplifications have since been made, no proof has been found that avoids the use of a computer.

This book, a translation of the authors' original German version, begins with an informal description of the origins of the problem and its historical development, complete with interesting biographies of the main players. Much of this material covers well-trodden ground and there are a number of mistakes and omissions, including inaccuracies in the treatment of 19th-century British mathematics.

Chapters two and three are devoted to the topological background needed for a serious study of the problem, with formal definitions of maps and boundary lines and a clear statement of what is to be proved. In chapters four and five the combinatorial aspects of the problem are fully discussed,and the appropriate graph-theoretical setting is presented. In a combinatorial context, the four-colour problem then becomes that of proving the existence in any map of an "unavoidable set of reducible configurations" - every map must contain at least one of these configurations of countries, and whichever one(s) may appear, a four-colouring of the map can then be shown to exist. In Appel and Haken's proof, their set contained nearly 2000 such configurations, explaining the necessity for many hundreds of hours of computer time. Chapters six and seven complete the story by describing in general terms how such a set can be constructed. This English edition concludes with a brief description of recent work by Neil Robertson, Daniel Sanders, Paul Seymour and Robin Thomas, in which the computer work is simplified so it can be read and checked by a computer in minutes. Their work can be viewed on the internet (http://www.math.gatech.edu/thomas/FC/fourcolor.html).

This is the fifth book to be dedicated entirely to the four-colour problem, and it is probably the best current introduction - the opening chapter is particularly impressive. Although the mathematical level is aimed at final-year undergraduate or first-year graduate students, readers without this background will find much of use in its pages.

Robin J. Wilson is senior lecturer in mathematics, Open University.