Four Color Theorem - History - Proof By Computer

Proof By Computer

During the 1960s and 1970s German mathematician Heinrich Heesch developed methods of using computers to search for a proof. Notably he was the first to use discharging for proving the theorem, which turned out to be important in the unavoidability portion of the subsequent Appel-Haken proof. He also expanded on the concept of reducibility and, along with Ken Durre, developed a computer test for it. Unfortunately, at this critical juncture, he was unable to procure the necessary supercomputer time to continue his work (Wilson 2002).

Others took up his methods and his computer-assisted approach. In 1976, while other teams of mathematicians were racing to complete proofs, Kenneth Appel and Wolfgang Haken at the University of Illinois announced that they had proven the theorem. They were assisted in some algorithmic work by John A. Koch (Wilson 2002).

If the four-color conjecture were false, there would be at least one map with the smallest possible number of regions that requires five colors. The proof showed that such a minimal counterexample cannot exist, through the use of two technical concepts (Wilson 2002; Appel & Haken 1989; Thomas 1998, pp. 852–853):

1. An unavoidable set contains regions such that every map must have at least one region from this collection.
2. A reducible configuration is an arrangement of countries that cannot occur in a minimal counterexample. If a map contains a reducible configuration, then the map can be reduced to a smaller map. This smaller map has the condition that if it can be colored with four colors, then the original map can also. This implies that if the original map can not be colored with four colors the smaller map can't either and so the original map is not minimal.

Using mathematical rules and procedures based on properties of reducible configurations, Appel and Haken found an unavoidable set of reducible configurations, thus proving that a minimal counterexample to the four-color conjecture could not exist. Their proof reduced the infinitude of possible maps to 1,936 reducible configurations (later reduced to 1,476) which had to be checked one by one by computer and took over a thousand hours. This reducibility part of the work was independently double checked with different programs and computers. However, the unavoidability part of the proof was verified in over 400 pages of microfiche, which had to be checked by hand (Appel & Haken 1989).

Appel and Haken's announcement was widely reported by the news media around the world, and the math department at the University of Illinois used a postmark stating "Four colors suffice." At the same time the unusual nature of the proof—it was the first major theorem to be proven with extensive computer assistance—and the complexity of the human verifiable portion, aroused considerable controversy (Wilson 2002).

In the early 1980s, rumors spread of a flaw in the Appel-Haken proof. Ulrich Schmidt at RWTH Aachen examined Appel and Haken's proof for his master's thesis (Wilson 2002, 225). He had checked about 40% of the unavoidability portion and found a significant error in the discharging procedure (Appel & Haken 1989). In 1986, Appel and Haken were asked by the editor of Mathematical Intelligencer to write an article addressing the rumors of flaws in their proof. They responded that the rumors were due to a "misinterpretation of results" and obliged with a detailed article (Wilson 2002, 225–226). Their magnum opus, a book claiming a complete and detailed proof (with a microfiche supplement of over 400 pages), appeared in 1989 and explained Schmidt's discovery and several further errors found by others (Appel & Haken 1989).