
related topics 
{math, number, function} 
{@card@, make, design} 
{area, part, region} 
{law, state, case} 
{work, book, publish} 
{style, bgcolor, rowspan} 
{son, year, death} 
{specie, animal, plant} 
{school, student, university} 
{county, mile, population} 

In mathematics, the four color theorem, or the four color map theorem states that, given any separation of a plane into contiguous regions, producing a figure called a map, no more than four colors are required to color the regions of the map so that no two adjacent regions have the same color. Two regions are called adjacent only if they share a border segment, not just a point. For example, Utah and Arizona are adjacent, but Utah and New Mexico, which only share a point, are not.
Despite the motivation from coloring political maps of countries, the theorem is not of particular interest to mapmakers. According to an article by the math historian Kenneth May (Wilson 2002, 2), "Maps utilizing only four colours are rare, and those that do usually require only three. Books on cartography and the history of mapmaking do not mention the fourcolor property."
Three colors are adequate for simpler maps, but an additional fourth color is required for some maps, such as a map in which one region is surrounded by an odd number of other regions that touch each other in a cycle. The five color theorem, which has a short elementary proof, states that five colors suffice to color a map and was proven in the late 19th century (Heawood 1890); however, proving that four colors suffice turned out to be significantly harder. A number of false proofs and false counterexamples have appeared since the first statement of the four color theorem in 1852.
The four color theorem was proven in 1976 by Kenneth Appel and Wolfgang Haken. It was the first major theorem to be proved using a computer. Appel and Haken's approach started by showing that there is a particular set of 1,936 maps, each of which cannot be part of a smallestsized counterexample to the four color theorem. Appel and Haken used a specialpurpose computer program to confirm that each of these maps had this property. Additionally, any map (regardless of whether it is a counterexample or not) must have a portion that looks like one of these 1,936 maps. To show this required hundreds of pages of hand analysis. Appel and Haken concluded that no smallest counterexamples existed because any must contain, yet not contain, one of these 1,936 maps. This contradiction means there are no counterexamples at all and that the theorem is therefore true. Initially, their proof was not accepted by all mathematicians because the computerassisted proof was infeasible for a human to check by hand (Swart 1980). Since then the proof has gained wider acceptance, although doubts remain (Wilson 2002, 216â€“222).
To dispel remaining doubt 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. Additionally in 2005, the theorem was proven by Georges Gonthier with general purpose theorem proving software.
Contents
Full article ▸


related documents 
Shell sort 
Selection sort 
Brouwer fixed point theorem 
Tree automaton 
Rootfinding algorithm 
Symmetric matrix 
Analytic function 
Tangent space 
Uniform convergence 
Naive Bayes classifier 
Orthogonality 
Embedding 
Octonion 
Pell's equation 
Burnside's problem 
Scientific notation 
Delaunay triangulation 
Sufficiency (statistics) 
Analytic continuation 
Total order 
MathML 
Fundamental theorem of arithmetic 
Befunge 
Partial derivative 
Inequality 
Curve 
Transcendental number 
Finite state machine 
Binomial theorem 
Tensor 
