Editing Conjecture (section)

===Four color theorem===
{{Main|Four color theorem}}
[[File:Map of United States vivid colors shown.png|thumb|A four-coloring of a map of the states of the United States (ignoring lakes).]]

In [[mathematics]], the [[four color theorem]], or the four color map theorem, states that given any separation of a plane into [[wikt:contiguity|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'' if they share a common boundary that is not a corner, where corners are the points shared by three or more regions.<ref>{{cite journal |title=Formal Proof—The Four-Color Theorem |author-link=Georges Gonthier|author=Georges Gonthier |journal=Notices of the AMS |volume=55 |issue=11 |date=December 2008 |pages=1382–1393|quote=From this paper: Definitions: A planar map is a set of pairwise disjoint subsets of the plane, called regions. A simple map is one whose regions are connected open sets. Two regions of a map are adjacent if their respective closures have a common point that is not a corner of the map. A point is a corner of a map if and only if it belongs to the closures of at least three regions. Theorem: The regions of any simple planar map can be colored with only four colors, in such a way that any two adjacent regions have different colors.}}</ref> For example, in the map of the United States of America, Utah and Arizona are adjacent, but Utah and New Mexico, which only share a [[Four Corners Monument|point]] that also belongs to Arizona and Colorado, are not.

[[August Ferdinand Möbius|Möbius]] mentioned the problem in his lectures as early as 1840.<ref name="rouse_ball_1960">[[W. W. Rouse Ball]] (1960) ''The Four Color Theorem'', in Mathematical Recreations and Essays, Macmillan, New York, pp 222-232.</ref> The conjecture was first proposed on October 23, 1852<ref name=MacKenzie>Donald MacKenzie, ''Mechanizing Proof: Computing, Risk, and Trust'' (MIT Press, 2004) p103</ref> when [[Francis Guthrie]], while trying to color the map of counties of England, noticed that only four different colors were needed. 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;<ref>{{Cite journal|last=Heawood|first=P. J.|date=1890|title=Map-Colour Theorems|journal=Quarterly Journal of Mathematics|location=Oxford|volume=24|pages=332–338}}</ref> however, proving that four colors suffice turned out to be significantly harder. A number of false proofs and false [[counterexample]]s have appeared since the first statement of the four color theorem in 1852.

The four color theorem was ultimately proven in 1976 by [[Kenneth Appel]] and [[Wolfgang Haken]]. It was the first major [[theorem]] to be [[computer-assisted proof#Theorems proved with the help of computer programs|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 smallest-sized counterexample to the four color theorem (i.e., if they did appear, one could make a smaller counter-example). Appel and Haken used a special-purpose computer program to confirm that each of these maps had this property. Additionally, any map that could potentially be a counterexample must have a portion that looks like one of these 1,936 maps. Showing this with hundreds of pages of hand analysis, Appel and Haken concluded that no smallest counterexample exists because any must contain, yet do 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 mathematicians at all because the [[computer-assisted proof]] was infeasible for a human to check by hand.<ref>{{Cite journal|last=Swart|first=E. R.|date=1980|title=The Philosophical Implications of the Four-Color Problem|journal=The American Mathematical Monthly|volume=87|issue=9|pages=697–702|doi=10.2307/2321855|issn=0002-9890|jstor=2321855}}</ref> However, the proof has since then gained wider acceptance, although doubts still remain.<ref>{{Cite book|title=Four colors suffice : how the map problem was solved|last=Wilson|first=Robin|publisher=Princeton University Press|year=2014|isbn=9780691158228|edition=Revised color|location=Princeton, New Jersey|pages=216–222|oclc=847985591}}</ref>