Ryan Proper Mysteries of Mathematics

December 14, 1999 Final Paper

Graph Theory: The Four Coloring Theorem

"Every planar map is four colorable," seems like a pretty basic and easily provable statement. However, this simple concept took over one hundred years and involved more than a dozen mathematicians to finally prove it. Throughout the century that many men pondered this idea, many other problems, solutions, and mathematical concepts were created. I find the Four Coloring Theorem to be very interesting because of it's apparent simplicity paired with it's long, laborious struggle to be proved. There is a very long and eventful history that accompanies this theorem.

The concept of the Four Coloring Theorem was born in 1852 when Francis Guthrie noticed that he only needed four different colors to color in a map of England. Through his brother, Frederick, Francis communicated his discovery to De Morgan. Francis wondered if De Morgan would be able to tell him if it was true or not. De Morgan was unsure, so he asked the same question to Hamilton in Dublin. Hamilton was unable to help, so De Morgan continued to ask other prominent mathematicians. In the US, Charles Peirce attempted to prove the Four Color Conjecture in the 1860's and continued to for the remainder of his life. In 1879, Cayley wrote a paper to the Royal Geographical Society explaining the difficulties in attempting to prove the Conjecture. On July 17, 1879, a mathematician by the name of Kempe announced a proof for the Four Color Conjecture. However, eleven years later Heawood, a lecturer at Durham England, pointed out that Kempe's proof was incorrect. Along with proving Kempe wrong, Heawood was able to prove that every planar map is five colorable. In 1898, Heawood also proved that if the number of edges around a region is divisible by three then the region is four colorable. In 1880 a man by the name of Tait came up with his own proof for the Four Color Conjecture. Once again the proof was proved false, this time by Petersen in 1891. In the midst of these two failed attempts at finding a proof for the Four Color Conjecture, Kempe and Tait both made other major contributions to the world of mathematics. Kempe discovered what would later become known as Kempe chains and Tait devised a equivalent form of the Four Color Theorem for three-edge-coloring. The next major contribution was the concept of reducibility by Birkoff. Using Birkoff's work, Franklin proved that any map with up to 25 regions can be four colorable in 1922. In 1926 Reynolds increased the number of regions to 27. Winn increased it to 35 in 1940, Ore and Stemple to 39 in 1970, and Mayer to 95 in 1976. Heesch later developed the two main concepts that eventually led to the final proof. They were reducibility and discharging. Finally, in 1976, Appel and Haken came up with a complete solution to the Four Color Conjecture basing their methods on reducibility using Kempe chains. The Four Color Theorem was the first major theorem to be proved using a computer. (Sources #4+#5)

Wolfgang Haken was born in Berlin on June 21, 1928. He studied mathematics, physics, and philosophy in Kiel. He received his doctorate in 1953 with a specialization in topology. In 1948 he attended a lecture in which Heesch presented some of his first deliberations and results. Haken worked in Munich as an engineer in the development of microwave technology for a company called Siemens & Halske from 1954 to 1962. Haken discovered a finite procedure for deciding whether a knot is knotted or unknotted. After this discovery he was invited as a visiting professor to the University of Illinois in Urbana. Haken was a temporary member of the Institute for Advanced Study in Princeton from 1963 to 1965. In 1965, he became a professor at the University of Illinois. In 1990, he was nominated for membership in the Center for Advanced Study, the highest honor granted for scientific achievement. In 1993, the Johann Wolfgang Goethe University in Frankfurt honored Haken with an honorary doctorate in recognition of his work, mostly for his work on three-dimensional manifolds, which later became known as Haken manifolds. (Source #1)

Kenneth Appel was born in Brooklyn, NY on November 8, 1932. He earned his bachelor of science degree from Queen's College of the City University of New York in 1953. Appel then went on to earn his master's degree from the University of Michigan in 1955. Throughout his mathematics career, Appel's research interests were from the theory of recursive functions to combinatorial group theory to combinatorics. Appel accumulated an interest in computers in 1956. In 1961, he became a full professor at the University of Illinois in Urbana. In 1971, he began to focus on the Four Color Problem. He was responsible for the programming of the discharging procedures. Since 1993, he has been the chairman of the department of mathematics at the University of New Hampshire. (Source #1)

In class we attempted to prove the Four Color Theorem by first changing it into a graph theory problem. Using a two dimensional map, we replaced all the countries by vertices. The outside surroundings of the map must also be counted as a country, and therefore it must also be represented as a vertex. We then connected pairs of vertices which had a common boundary line. However, we did not connect the vertices which only had a common boundary point. Next we colored each vertex a different color so that no two vertices sharing a common edge would also share a common color. Using as few colors as possible we realized that this can be done with only four colors. This became more evident when we colored each country the color of their corresponding vertex. After doing this, we came to the conclusion that we could not prove the Four Color Theorem by using a graph theory problem. Since we reached a dead end, we decided to try a different route of attack by beginning with the Six Color Theorem. If we could prove the Six Color Theorem then we could move to trying to prove the Five Color Theorem and then eventually reach our goal of proving the Four Color Theorem. This also could result in some useful information being learned when trying to prove the Six or Five Color Theorem which could then be used to prove the Four Color Theorem.

To prove the Six Color Theorem we began by making a Lemma which states that, "At least one vertex of a planar graph has order five or less." The order of a vertex is the number of edges coming out of that vertex. Now to prove this lemma we must prove that the exact opposite of the lemma is false. We assume that we have a graph which satisfies the opposite of the lemma. We then form inequalities with the sum of the order of all faces in terms of faces and edges, and also with the sum of the order of all vertices in terms of vertices and edges. These inequalities then lead to a contradiction to Euler's Formula. Therefore the lemma must be correct. To show the Six Color Theorem, we pick a vertex of order five or less and delete that vertex and all edges leading into it. This is repeated until only six vertices are left. We then color the six remaining vertices six different colors. Then replacing each removed vertex and it's edges in reverse order of taking them out we color them a color which is not used in any of the at most five connecting vertices.

The Five Color Theorem is very similar to the Six Color Theorem. The only major difference is that the replacing of the removed vertices must be done more carefully. If the vertices are not replaced properly a problem could occur where five vertices are all colored the five different available colors leaving no color left for the middle vertex. The proof is done just like the Six Color Theorem proof. Instead of going through the same proof again, I will just point out the major difference which come about when replacing the removed vertices. As these vertices are being replaced some of the colors may need to be changed. This will reduce the colors of the vertices which are connected to the central vertex. As long as all of the outside vertices can be replaced using only four colors then there will be a fifth color left for the central vertex. This proves that only five colors are necessary to color any planar map. Therefore, the Five Color Theorem is proved to be true. (Source #2)

I find these problems to be very interesting and actually quite fun as well. They don't really have a real importance in the real world. The Four Color Theorem isn't going to save any lives or make life that much easier. However, it does make map coloring more simple by requiring only four colors.

Bibliography

(1) Fritsh, Rudolf and Gerda, The Four-Color Theorem, Springer-Verlag, New York, Inc., 1998.

(2) Harary, Frank, Graph Theory, Adison-Wesley Publishing Co., Redding, MA, 1972, p.130-131.

(3) Kainen, Paul, and Saaty, Thomas, The Four Color Problem, McGraw-Hill, Inc., Great Britain, 1977.

(4) The Four Color Theorem, http://www-groups.dcs.st-and.ac.uk/~history/HistTopics/The_four_colour_theorem.html, December 10, 1999.

(5) The Four Color Theorem, Neil Robertson, Daniel P. Sanders, Paul Seymour, and Robin Thomas, http://www.math.gatech.edu/~thomas/FC/fourcolor.html, December 10, 1999.