Four color theorem
This was improved upon in 1997 by Robertson, Sanders, Seymour, and Thomas, who have managed to decrease the number of such configurations to 633 – still an extremely long case analysis.
[4] (To be safe, we can restrict to regions whose boundaries consist of finitely many straight line segments.
At the time, Guthrie's brother, Frederick, was a student of Augustus De Morgan (the former advisor of Francis) at University College London.
According to De Morgan: A student of mine [Guthrie] asked me to day to give him a reason for a fact which I did not know was a fact—and do not yet.
[10] Another early published reference by Arthur Cayley (1879) in turn credits the conjecture to De Morgan.
Now this principle, that four areas cannot each have common boundary with all the other three without inclosure, is not, we fully believe, capable of demonstration upon anything more evident and more elementary; it must stand as a postulate.
[13] Tait, in 1880, showed that the four color theorem is equivalent to the statement that a certain type of graph (called a snark in modern terminology) must be non-planar.
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.
While other teams of mathematicians were racing to complete proofs, Kenneth Appel and Wolfgang Haken at the University of Illinois announced, on June 21, 1976,[17] that they had proved the theorem.
[18] 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:[19] 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.
However, the unavoidability part of the proof was verified in over 400 pages of microfiche, which had to be checked by hand with the assistance of Haken's daughter Dorothea Blostein.
[20] Appel and Haken's announcement was widely reported by the news media around the world,[21] and the math department at the University of Illinois used a postmark stating "Four colors suffice.
"[22] At the same time the unusual nature of the proof—it was the first major theorem to be proved with extensive computer assistance—and the complexity of the human-verifiable portion aroused considerable controversy.
Ulrich Schmidt at RWTH Aachen had examined Appel and Haken's proof for his master's thesis that was published in 1981.
[24] 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 replied that the rumors were due to a "misinterpretation of [Schmidt's] results" and obliged with a detailed article.
[20] Since the proving of the theorem, a new approach has led to both a shorter proof and a more efficient algorithm for 4-coloring maps.
[28] The following discussion is a summary based on the introduction to Every Planar Map is Four Colorable (Appel & Haken 1989).
Although flawed, Kempe's original purported proof of the four color theorem provided some of the basic tools later used to prove it.
Because of the large number of distinct four-colorings of the ring, this is the primary step requiring computer assistance.
As long as some member of the unavoidable set is not reducible, the discharging procedure is modified to eliminate it (while introducing other configurations).
Verifying the volume describing the unavoidable configuration set itself was done by peer review over a period of several years.
The four color theorem has been notorious for attracting a large number of false proofs and disproofs in its long history.
[21] Some alleged proofs, like Kempe's and Tait's mentioned above, stood under public scrutiny for over a decade before they were refuted.
This upper bound of 7 is sharp: certain toroidal polyhedra such as the Szilassi polyhedron require seven colors.
[34] Dror Bar-Natan gave a statement concerning Lie algebras and Vassiliev invariants which is equivalent to the four color theorem.
According to an article by the math historian Kenneth May, "Maps utilizing only four colors are rare, and those that do usually require only three.
[36] The theorem also does not guarantee the usual cartographic requirement that non-contiguous regions of the same country (such as the exclave Alaska and the rest of the United States) be colored identically.
