History of the FourColor Conjecture 18402004by Clarence WilliamsOne 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 fourcolor 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 [1], 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 fourcolor conjecture for the plane was August Ferdinand Moebius in 1840 [2]. 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 fourcolor conjecture remained unproven. In 1976, K. Appel and W. Haken [3][4] announced a "computer proof" of the fourcolor 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 fourcolor 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" [4]. 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 [6] announced a new proof of the fourcolor 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.
References
