Graph Theory: The Four Coloring Theorem Essay

1550 Words 7 Pages
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
…show more content…
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

Related Documents