Since then the proof has gained wide acceptance, although some doubters remain. The four color theorem was proved in 1976 by Kenneth Appel and Wolfgang Haken after many false proofs and counterexamples (unlike the five color theorem, proved in the 1800s, which states that five colors are enough to color a map).
In graph-theoretic terminology, the four-color theorem states that the vertices of every planar graph can be colored with at most four colors so that no two adjacent vertices receive the same color, or for short: Every planar graph is four-colorable. ==History== ===Early proof attempts=== As far as is known, the conjecture was first proposed on October 23, 1852, when Francis Guthrie, while trying to color the map of counties of England, noticed that only four different colors were needed.
Francis inquired with Frederick regarding it, who then took it to De Morgan (Francis Guthrie graduated later in 1852, and later became a professor of mathematics in South Africa).
Query cannot a necessity for five or more be invented…" "F.G.", perhaps one of the two Guthries, published the question in The Athenaeum in 1854, and De Morgan posed the question again in the same magazine in 1860.
Query cannot a necessity for five or more be invented…" "F.G.", perhaps one of the two Guthries, published the question in The Athenaeum in 1854, and De Morgan posed the question again in the same magazine in 1860.
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. One alleged proof was given by Alfred Kempe in 1879, which was widely acclaimed; another was given by Peter Guthrie Tait in 1880.
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. One alleged proof was given by Alfred Kempe in 1879, which was widely acclaimed; another was given by Peter Guthrie Tait in 1880.
Such examples were known to Fredrick Guthrie in 1880 .
Heawood in 1890 and, after contributions by several people, proved by Gerhard Ringel and J.
The only exception to the formula is the Klein bottle, which has Euler characteristic 0 (hence the formula gives p = 7) but requires only 6 colors, as shown by Philip Franklin in 1934. For example, the torus has Euler characteristic χ = 0 (and genus g = 1) and thus p = 7, so no more than 7 colors are required to color any map on a torus.
Since then the proof has gained wide acceptance, although some doubters remain. The four color theorem was proved in 1976 by Kenneth Appel and Wolfgang Haken after many false proofs and counterexamples (unlike the five color theorem, proved in the 1800s, which states that five colors are enough to color a map).
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, that they had proved the theorem.
Ulrich Schmidt at RWTH Aachen had examined Appel and Haken's proof for his master's thesis that was published in 1981 .
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.
Their magnum opus, Every Planar Map is Four-Colorable, a book claiming a complete and detailed proof (with a microfiche supplement of over 400 pages), appeared in 1989; it explained and corrected the error discovered by Schmidt as well as several further errors found by others . ===Simplification and verification=== Since the proving of the theorem, efficient algorithms have been found for 4-coloring maps requiring only O(n2) time, where n is the number of vertices.
In 1996, Neil Robertson, Daniel P.
To dispel any remaining doubts about the Appel–Haken proof, a simpler proof using the same ideas and still relying on computers was published in 1997 by Robertson, Sanders, Seymour, and Thomas.
In 2001, the same authors announced an alternative proof, by proving the snark conjecture.
This proof remains unpublished, however. In 2005, Benjamin Werner and Georges Gonthier formalized a proof of the theorem inside the Coq proof assistant.
All text is taken from Wikipedia. Text is available under the Creative Commons Attribution-ShareAlike License .
Page generated on 2021-08-05