 History of the Four-Color Conjecture 1840-2004

by Clarence Williams One of the most famous problems in mathematics arises when a surface is partitioned into regions. In combinatorial topology partitions of arbitrary surfaces are encountered whenever a curved surface is replaced by a topologically equivalent polyhedron. To obtain the faces of the polyhedron, one must first partition the curved surface into regions. The coloring problem is, then, to color all regions of the partition such that regions sharing a common boundary curve are assigned different colors, using the least possible number of colors. When the surface under consideration is the plane, we find an example of such a partition in ordinary geographical maps and the coloring problem is one of practical cartography. The four-color conjecture proposes that for the plane, the least number of colors that will suffice to color the regions in every conceivable partition of the surface without violation of the above rule is four. According to David Hilbert , a particularly conspicuous feature of the coloring problem is the difficulty of proving the conjecture in the case of the plane surface, where the result seems intuitively the most obvious. Similar results are easily proved for some surfaces of higher genus like the torus. The first mathematician to propose the four-color conjecture for the plane was August Ferdinand Moebius in 1840 . The problem seems to have been largely ignored from then until 1856 when two students of Augustus De Morgan, Francis and Frederick Guthrie asked their teacher about it. De Morgan was puzzled and wrote to William Rowan Hamilton, who at the time was very busy, and the problem remained unsolved. Subsequently, a host of famous mathematicians tried to prove the conjecture, until Alfred Bray Kempe announced a "proof" that was published in the American Journal of Mathematics in 1879. In 1890, Percy John Heawood showed that Kempe’s "proof" was wrong. Thus the four-color conjecture remained unproven. In 1976, K. Appel and W. Haken  announced a "computer proof" of the four-color conjecture, using 1200 hours of computer calculations that could not be verified by humans, even in principle. Even if their "proof" were somehow verified, it could never give any compelling reason for the validity of the four-color conjecture. As one critic put it, "a good mathematical proof is like a poem - this is a telephone directory!". In 1997, N. Robertson, D. P. Sanders, P. D. Seymour and R. Thomas announced a "simpler computer proof" . Their proof is also not humanly verifiable and brings the philosophical status of such "proofs" into doubt! What is more, the above "proofs" give no insight into why exactly four colors suffice to color any conceivable map drawn on the plane. In 2000, Ashay Dharwadker  announced a new proof of the four-color theorem that appears to have stood the test of time. Some notes on Dharwadker's proof: In section I on Map Coloring, he defines maps on the sphere and their proper coloring. For purposes of proper coloring it is equivalent to consider maps on the plane and furthermore, only maps which have exactly three edges meeting at each vertex. Lemma 1 proves the six colour theorem using Euler’s formula, showing that any map on the plane may be properly colored by using at most six colours. Dharwadker then makes the following definitions.

1. Define N to be the minimal number of colors required to properly color any map from the class of all maps on the plane.
2. Based on the definition of N, select a specific map m(N) on the plane which requires no fewer than N colors to be properly colored.
3. Based on the definition of the map m(N), select a proper coloring of the regions of the map m(N) using the N colors 0,1,...,N-1.
The rest of the proof works with the fixed number N, the fixed map m(N) and the fixed proper coloring of the regions of the map m(N). In section II Dharwadker defines Steiner Systems and prove Tits’ inequality and its consequence that if a Steiner system S(N+1,2N,6N) exists, then N cannot exceed 4. Now his goal is to demonstrate the existence of such a Steiner system. In section III he defines Eilenberg Modules. The regions of the map m(N) are partitioned into disjoint, nonempty equivalence classes 0,1,..., N-1 according to the color they receive. This set is given the structure of the cyclic group ZN={0,1,..., N-1} under addition modulo N. Now regard ZN as an Eilenberg module for the symmetric group S3 on three letters and consider the split extension ZN]S3 corresponding to the trivial representation of S3. By section IV on Hall Matchings he is able to choose a common system of coset representatives for the left and right cosets of S3 in the full symmetric group on |ZN]S3| letters. For each such common representative and for each ordered pair of elements of S3, in section V on Riemann Surfaces he establishes a certain action of the two-element cyclic group on twelve copies of the partitioned map m(N) by using the twenty-fourth root function of the sheets of the complex plane. Using this action, Dharwadker's section VI gives the details of the Main Construction. The 6N elements of ZN]S3 are regarded as the set of points and lemma 23 builds the blocks of 2N points with every set of N+1 points contained in a unique block. This constructs a Steiner system S(N+1,2N,6N) which implies by Tits’ inequality that N cannot exceed 4, completing the proof .

References

  David Hilbert and S. Cohn-Vossen, Anschauliche Geometrie, Goettingen, 1932.  Richard Courant and Herbert Robbins, What is Mathematics?, Oxford University Press, 1941.  K. Appel and W. Haken, Every planar map is four colorable. Part I. Discharging, Illinois J. Math. 21 (1977), 429-490.  K. Appel, W. Haken and J. Koch, Every planar map is four colorable. Part II. Reducibility, Illinois J. Math. 21 (1977), 491-567.  N. Robertson, D. P. Sanders, P. D. Seymour and R. Thomas, The four color theorem, J. Combin. Theory Ser. B. 70 (1997), 2-44.  Ashay Dharwadker, A New Proof of the Four Colour Theorem, http://www.geocities.com/dharwadker/ , 2000.  Robert Stewart, A Review of Dharwadker's Proof, http://fourcolourtheorem.tripod.com/ , 2005.