Four color theorem
In mathematics, the four color theorem, or the four color map theorem, states that no more than four colors are required to color the regions of any map so that no two adjacent regions have the same color. Adjacent means that two regions share a common boundary of non-zero length (i.e., not merely a corner where three or more regions meet).[1] It was the first major theorem to be proved using a computer. Initially, this proof was not accepted by all mathematicians because the computer-assisted proof was infeasible for a human to check by hand.[2] The proof has gained wide acceptance since then, although some doubts remain.[3]
The theorem is a stronger version of the five color theorem, which can be shown using a significantly simpler argument. Although the weaker five color theorem was proven already in the 1800s, the four color theorem resisted until 1976 when it was proven by Kenneth Appel and Wolfgang Haken. This came after many false proofs and mistaken counterexamples in the preceding decades.
The Appel-Haken proof proceeds by analyzing a very large number of reducible configurations. 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. In 2005, the theorem was verified by Georges Gonthier using a general-purpose theorem-proving software.
A radially symmetric 7-colored torus – regions of the same colour wrap around along dotted lines
An 8-coloured double torus (genus-two surface) – bubbles denote unique combination of two regions
Tietze's subdivision of a Möbius strip into six mutually adjacent regions, requiring six colors. The vertices and edges of the subdivision form an embedding of Tietze's graph onto the strip.
Interactive Szilassi polyhedron model with each of 7 faces adjacent to every other – in the SVG image, move the mouse to rotate it
Relation to other areas of mathematics[edit]
Dror Bar-Natan gave a statement concerning Lie algebras and Vassiliev invariants which is equivalent to the four color theorem.[35]
Use outside of mathematics[edit]
Despite the motivation from coloring political maps of countries, the theorem is not of particular interest to cartographers. 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. Books on cartography and the history of mapmaking do not mention the four-color property".[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.