# The Four Color Map Problem by Sharon Murray

The four-color-map problem was first pondered by Francis Guthrie in 1852. Francis Guthrie proposed that every map can be colored with only four colors in such a way that countries sharing a common border have different colors. More than a century later, in 1976, the four-color problem was solved by Kenneth Appel and Wolfgang Haken.
The proof of the four-color solution made unprecedented use of computers. Appel and Haken admitted in 1977 that it was not yet known whether there is any proof of the four-color-map solution that is “elegant, concise and completely comprehensible by a human mathematical mind.” Now, in 2006, we still do not yet know if such a proof is possible.
A peer of Francis Guthrie, Augustus DeMorgan, proved that it is not possible for five countries to be in a position such that each of them is adjacent to the other four. However, proving that five mutually adjacent countries cannot exist in a map does not prove the four-color conjecture.
In 1879, Alfred Kempe published a paper purporting to show that the four-color conjecture is true. Although his proof turned out to be incomplete, it contained most of the basic ideas that led to the correct proof by Appel and Haken. Kempe set out to prove the four color conjecture by proving that a minimal five-chromatic map is impossible. Kempe correctly proved that a country with two, three or four neighbors existing in a minimal five-chromatic map leads to contradiction, but his proof of the case of five neighbors was faulty.
The two important ideas that are basic to the Appel-Haken proof are “unavoidability” and “reducibility.” Unavoidability is the idea that every normal map must contain at least one of four configurations. Reducibility is the idea that a configuration is reducible if there is a way of showing that the configuration cannot possibly appear in a minimal five-chromatic map.
Appel and Haken attacked the four-color problem by constructing an unavoidable set of reducible configurations. The set consisted of some 1500 complex configurations. Appel and Haken state that to show large configurations are reducible requires the examination of a large number of details and appears feasible only by computer.
In 1996, Neil Robertson, Daniel P. Sanders, Paul Seymour, and Robin Thomas worked out their own proof of the four-color-problem <http://www.math.gatech.edu/~thomas/FC/fourcolor.html>. The basic idea of their proof is the same as Appel and Haken’s. However, instead of some 1500 complex configurations, their proof consists of a set of 663 unavoidable configurations. Robertson, Sanders, Seymour and Thomas obtain a quadratic algorithm to four-color planar graphs. They propose that this is an improvement over the quartic algorithm of Appel and Haken. As with the Appel and Haken proof, the Robertson, Sanders, Seymour and Thomas proof contains steps that can never be verified by hand.
The fact that the Appel and Haken proof as well as the Robertson, Sanders, Seymour and Thomas proof are not hand checkable is still a source of irritation to some mathematicians. On the internet, there are many examples of professional mathematicians and amateur mathematicians attempting to prove the four-color conjecture in a short proof that can be “completely comprehensible by a human mathematical mind.” One such example is that of Howard Levi’s unfinished work.
Howard Levi attempted to devise a proof of the four-color theorem of a traditional kind (not involving extensive use of computers). He formulated an algebraic equivalent which he tried to prove without success. When Howard died in 2002, his work was left unfinished. Friends and colleagues posted Levi’s work to the internet in the hopes that someone can use his work to prove, algebraically, the four-color theorem. http://64.233.161.104/search?q=cache:h627VeWI5BoJ:comet.lehman.cuny.edu/fitting/fourcolor/Howard/fourcolor.pdf+Levi+%22Four+Color+Map%22+site:.edu&hl=en&gl=us&ct=clnk&cd=1&ie=UTF-8.
Even though the four-color-map problem was solved in 1976, it is evident that much of the mathematical community remains unsatisfied. The “elegant” proof, if possible, has not yet been found.

References:

1. Appel, Kenneth and Haken, Wolfgang. “The Solution of the Four-Color-Map Problem,” Scientific American, Volume 237 (1977): 108-121.

2. Thomas, Robin. “The Four Color Theorem,” Math.gatech.edu. 13 Nov 1995.

Robin Thomas is currently a professor of mathematics at the Georgia Institute of Technology.

3. Coppersmith, Don; Fitting, Melvin; and Meyer, Paul. “An Algebraic Reformulation of the Four Color Theorem.” 31 Jan 2003. <http://64.233.161.104/search?q=cache:h627VeWI5BoJ:comet.lehman.cuny.edu/

fitting/fourcolor/Howard/fourcolor.pdf+Levi+%22Four+Color+Map%22+site:.edu

&hl=en&gl=us&ct=clnk&cd=1&ie=UTF-8>
Melvin Fitting and Paul Meyer state that they are from CUNY and Don Coppersmith states that he is from IBM.