Introduction
In 1852, Francis Guthrie was discussing with his brother Frederick the coloring of a map. He discovered the fact that he could color the map of England counties with the use of only four colors. He used the colors in such a way that each division had a single color and two segments sharing a common boundary had different colors. Thus, the four color problem was born and the question arose whether in a plane map, four colors were sufficient to denote the divisions of adjacent regions sharing the same boundary, without using the same colors.
Early Proofs
A.B. Kempe is regarded as the first person who gave a published proof regarding the four color problem. The American Journal of Mathematics, in 1879, published the work of A.B. Kempe proving that any map on the surface of a sphere could be four colored. In 1976, Kenneth Appel and Wolfgang Haken, with the help of the computer, proved the theorem based on the properties of reducible configurations and unavoidability. They showed that these two concepts can be employed as a tool only if there is a finite set of labeled planar graphs known as configurations. The potential maps were finitely reduced to 1936 configurations and were further abridged to 1476. They checked the configurations and the reducibility properties by a computer and verified the unavoidability factor manually. Appel and Haken now concluded and proved that the theorem was true because there were no smallest counterexamples to any of these 1476 maps.
Going a step forward, in 1997, in the Journal of Combinatorial Theory authors Neil Robertson, Daniel Sanders, Paul Seymour, and Robin Thomas developed an efficient algorithm based on Appel and Haken’s proof. The proof required checking only 633 configurations thus reducing the complexity of the problem. It also used the unavoidability and reducibility technique and used the computer to verify the theorem.
Development of the theorem
Kempe, in 1879, came out with a solution for the four color problem. He used a method popularly known as “Kempe Chains” for the proof. According to Kempe, in a map, if every segment is colored with one of the colors like orange, violet, brown and ochre, and one segment named O is left uncolored, and if this segment O is not encircled by the other four colored segments, then in that case there is a color left for O. If we label the regions as E,F,G,H, surrounding O and color them as orange, ochre, violet and brown respectively then there are two cases to reflect on;
1. No adjoining segments from E to G are alternatively colored orange and violet and no chain is formed
2. The adjacent segments from E to G are alternately colored orange and violet and a chain is formed
If case one holds well, then change the segment E to violet and exchange the color of orange/violet in the chain of segments joining E. As G is not part of the chain it retains color violet and because there is no orange segment adjacent to O then O can be colored orange.
If case two holds true then there can be no ochre/brown adjacent segments from F to H as crossing the segments of orange/violet segments is not possible. Case one holds good for F and H and we can change the colors as mentioned therein.
But in 1890 Heawood found a flaw in Kempe’s proof. He proved that every map can be five- colored. Heawood dedicated his life to map coloring. He further proved that if the number of edges around each segment is divisible by three, then the segments can be fully covered using only four colors.
Heesch; in 1969, was the first person to use the method of discharging, to prove the theorem. He believed that the four color problem can be solved by considering a set of 8900 configurations. He used the Kempe chain arguments to test the reducibility and developed a computer test for it. Unfortunately; at a very crucial stage; he was not able to get hold of the necessary advanced computer time to carry on his work of reducibility.
In 1976 the four color problem, which had become the four color theorem, was, solved once again. Appel and Haken, using the Kempe chains for reducibility, and with the help of Heesch’s ideas, created a set of about 1500 configurations. The total boundary size was comparatively reduced to less than 14. Appel and Haken worked through the details of final proof. Through all this, they were ably supported by Koch who helped them with the computer work. This was the first time any theorem was proved with the help of a computer.
References
1. Wikipedia. “Four color theorem”. 18th April 2014. http://en.wikipedia.org/wiki/Four_color_theorem
2. J J O'Connor and E F Robertson. “The four colour theorem”. September 1996. 18th April 2014. http://www-history.mcs.st-andrews.ac.uk/HistTopics/The_four_colour_theorem.html
3. Al Adeh, Fayez Fok. "A Pure Mathematical Proof of the Four Color Problem."Proceedings of the World Congress on Engineering and Computer Science. Vol. 1. 2011.
4. Appel, Kenneth, and Wolfgang Haken. "Every planar map is four colorable. Part I: Discharging." Illinois Journal of Mathematics 21.3 (1977): 429-490.
5. Appel, Kenneth, Wolfgang Haken, and John Koch. "Every planar map is four colorable. Part II: Reducibility." IllinoisJournal of Mathematics 21.3 (1977): 491-567.
6. Appel, Kenneth I., and Wolfgang Haken. Every planar map is four colorable. Vol. 98. Providence, RI: American mathematical society, 1989.
7. Davidson, Ruth. "The 150 Year Journey of the Four Color Theorem."
8. K. Appel and W. Haken, ‘Every map is four colourable’, Bulletin of the American
Mathematical Society 82 (1976), 711–12.
9. Mitchem, John. "On the history and solution of the four-color map problem."Two-Year College Mathematics Journal (1981): 108-116.
