Example of a four-colored map

The four color theorem (also known as the four color map theorem) states that given any plane separated into regions, such as a political map of the states of a country, the regions may be colored using no more than four colors in such a way that no two adjacent regions receive the same color. Two regions are called adjacent only if they share a border segment, not just a point (so the U.S. states of Utah and New Mexico are not deemed adjacent, even though they meet at the Four Corners). Each region must be contiguous: that is, it may not have exclaves like some real countries such as Angola, Azerbaijan, or the United States. Image File history File links Four_Colour_Map_Example. ... Image File history File links Four_Colour_Map_Example. ... Official language(s) English Capital Salt Lake City Largest city Salt Lake City Area  Ranked 13th  - Total 84,889 sq mi (219,887 km²)  - Width 270 miles (435 km)  - Length 350 miles (565 km)  - % water 3. ... Capital Santa Fe Largest city Albuquerque Area  Ranked 5th  - Total 121,665 sq mi (315,194 km²)  - Width 342 miles (550 km)  - Length 370 miles (595 km)  - % water 0. ... The Four Corners region is in the red area on this map The Four Corners Monument, placed by the Interior Department at the exact point. ... This article or section does not cite any references or sources. ... D is Bs exclave, but is not an enclave. ...

It is often the case that using only three colors is inadequate. This applies already to the map with one region surrounded by three other regions (even though with an even number of surrounding countries three colors are enough) and it is not at all difficult to prove that five colors are sufficient to color a map. The five color theorem in graph theory states that any map can be colored with no more than five colors. ...

The four color theorem was the first major theorem to be proven using a computer, and the proof is not accepted by all mathematicians because it would be unfeasible for a human to verify by hand (see computer-assisted proof). Ultimately, in order to believe the proof, one has to have faith in the correctness of the compiler and hardware executing the program used for the proof. Look up theorem in Wiktionary, the free dictionary. ... A computer-assisted proof is a mathematical proof that has been generated by computer. ... A diagram of the operation of a typical multi-language, multi-target compiler. ... For other uses, see Hardware (disambiguation). ...

The perceived lack of mathematical elegance by the general mathematical community was another factor, and to paraphrase comments of the time, "a good mathematical proof is like a poem—this is a telephone directory!"^{[citation needed]} In mathematics, a proof is a demonstration that, assuming certain axioms, some statement is necessarily true. ... Moscow phone book, 1930. ...

History

The conjecture was first proposed in 1852 when Francis Guthrie, while trying to color the map of counties of England, noticed that only four different colors were needed. At the time, Guthrie was a student of Augustus De Morgan at University College. (Guthrie graduated later in 1852, and later became a professor of mathematics in South Africa). According to De Morgan: In mathematics, a conjecture is a mathematical statement which appears likely to be true, but has not been formally proven to be true under the rules of mathematical logic. ... Example of a four color map The four color theorem states that every possible geographical map can be colored with at most four colors in such a way that no two adjacent regions receive the same colour. ... Motto (French) God and my right Anthem No official anthem - the United Kingdom anthem God Save the Queen is commonly used England() – on the European continent() – in the United Kingdom() Capital (and largest city) London (de facto) Official languages English (de facto)1 Unified  -  by Athelstan 927 AD  Area  -  Total... Augustus De Morgan (June 27, 1806 – March 18, 1871) was an Indian-born British mathematician and logician. ... The Front Quad University College London, commonly known as UCL, is one of the colleges that make up the University of London. ...

A student of mine [Guthrie] asked me today to give him a reason for a fact which I did not know was a fact - and do not yet. He says that if a figure be anyhow divided and the compartments differently coloured so that figures with any portion of common boundary line are differently coloured - four colours may be wanted, but not more—the following is the case in which four colours are wanted. Query cannot a necessity for five or more be invented…

The first published reference is by Arthur Cayley,^[1] who in turn credits the conjecture to De Morgan. Arthur Cayley (August 16, 1821 - January 26, 1895) was a British mathematician. ...

There were several early failed attempts at proving the theorem. One proof of the theorem was given by Alfred Kempe in 1879, which was widely acclaimed; another proof was given by Peter Guthrie Tait in 1880. It wasn't until 1890 that Kempe's proof was shown incorrect by Percy Heawood, and 1891 that Tait's proof was shown incorrect by Julius Petersen—each false proof stood unchallenged for 11 years. Look up theorem in Wiktionary, the free dictionary. ... In mathematics, a proof is a demonstration that, assuming certain axioms, some statement is necessarily true. ... Sir. ... Peter Tait Peter Guthrie Tait (April 28, 1831 - July 4, 1901) was a Scottish mathematical physicist. ... Percy John Heawood (1861-1955) was a British mathematician. ... Julius Peter Christian Petersen (June 16, 1839 - August 5, 1910) was a Danish mathematician. ...

In 1890, in addition to exposing the flaw in Kempe's proof, Heawood proved that all planar graphs are five-colorable; see five color theorem. In graph theory, a planar graph is a graph that can be drawn so that no edges intersect (or that can be embedded) in the plane. ... The five color theorem in graph theory states that any map can be colored with no more than five colors. ...

Significant results were produced by Croatian mathematician Danilo Blanuša in the 1940s by finding an original snark. Danilo BlanuÅ¡a (December 7, 1903 - August 8, 1987) was a Croatian mathematician, physicist, engineer and a professor at the University of Zagreb. ... In graph theory, a snark is a connected, bridgeless cubic graph with chromatic index equal to four. ...

During the 1960s and 1970s German mathematician Heinrich Heesch developed methods of applying the computer in searching for a proof. Heinrich Heesch (* June 25th 1906 in Kiel, † July 26th 1995 in Hannover) was a German mathematician. ... The NASA Columbia Supercomputer. ...

It was not until 1976 that the four-color conjecture was finally proven by Kenneth Appel and Wolfgang Haken at the University of Illinois. They were assisted in some algorithmic work by John Koch. Kenneth Appel (born 1932) is a mathematician who, in 1976 with colleague Wolfgang Haken at the University of Illinois at Urbana-Champaign, solved one of the most famous problems in mathematics, the four-color theorem. ... Wolfgang Haken (born June 21, 1928) is a mathematician who specialized in topology, in particular 3-manifolds. ... The University of Illinois at Urbana-Champaign (UIUC), is the largest campus in the University of Illinois system. ... An editor has expressed a concern that the subject of the article does not satisfy the notability guideline or one of the following guidelines for inclusion on Wikipedia: Biographies, Books, Companies, Fiction, Music, Neologisms, Numbers, Web content, or several proposals for new guidelines. ...

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:

• An unavoidable set contains regions such that every map must have at least one region from this collection.
• A reducible configuration is an arrangement of countries that cannot occur in a minimal counterexample. If a map contains a reducible configuration, and the rest of the map can be colored with four colors, then the entire map can be colored with four colors and so this map is not minimal.

Using mathematical rules and procedures based on properties of reducible configurations (e.g. the method of discharging, rings, Kempe chains, etc.), Appel and Haken found an unavoidable set of reducible configurations, thus proving that a minimal counterexample to the four-color conjecture could not exist. Their proof reduced the infinitude of possible maps to 1,936 reducible configurations (later reduced to 1,476) which had to be checked one by one by computer. This reducibility part of the work was independently double checked with different programs and computers. However, the unavoidability part of the proof was over 500 pages of hand written counter-counter-examples, much of which was Haken's teenage son Lippold verifying graph colorings. The computer program ran for hundreds of hours. The discharging method is a technique used to prove lemmas in structural graph theory. ... A 3-coloring suits this graph, but fewer colors would result in adjacent vertices of the same color. ...

Since the proving of the theorem, efficient algorithms have been found for 4-coloring maps requiring only O(n²) time, where n is the number of vertices. In 1996, Neil Robertson, Daniel P. Sanders, Paul Seymour and Robin Thomas created a quadratic time algorithm, utilizing Belaga's work and improving on a quartic algorithm based on Appel and Haken’s proof. This efficiency increase was due to their new proof, which was similar to Appel and Haken's proof but reduced the complexity of the problem and required checking only 633 reducible configurations. Both the unavoidability and reducibility parts of this new proof required the use of a computer and are impractical for humans to check by hand. Year 1996 (MCMXCVI) was a leap year starting on Monday (link will display full 1996 Gregorian calendar). ... Neil Robertson is a mathematician working mainly in topological graph theory, currently teaching at the Ohio State University. ... Paul Seymour (born July 26, 1950) is a mathematician working in graph theory, combinatorics and optimization and discrete mathematics at Princeton University, Princeton, New Jersey, United States. ... Edward Grigorievich Belaga (also Eduard Belaga) (born 22 December 1939) is a Russian mathematician. ...

In 1980 British polymath George Spencer-Brown deposited his alleged "proof" of the four color map theorem at the Royal Society. The purported proof, included completely in English in the German version of his book "Laws of Form", Lübeck 1997, Appendix 5, is not thought to be valid. Leonardo da Vinci, a polymath, is seen as the epitome of the Renaissance Man A polymath (Greek polymathÄ“s, πολυμαθής, meaning having learned much)[1], Renaissance man or Homo universalis are common terms to describe a person well educated, or who excels, in a wide variety of subjects or fields. ... G. Spencer-Brown (April 2, 1923) was born in Grimsby, Lincolnshire, England and is a British mathematician. ... The book Laws of Form (hereinafter abbreviated LoF), by G. Spencer-Brown, describes three distinct logical systems: The primary arithmetic (described in Chapter 4), which can be interpreted as Boolean arithmetic; The primary algebra (Chapter 6), which can be interpreted via two-element Boolean algebra (hereinafter abbreviated 2), Boolean logic...

In 2004 Benjamin Werner and Georges Gonthier formalized a proof of the theorem inside the Coq proof assistant (Gonthier, n.d.). This removes the need to trust the various computer programs used to verify particular cases — it is only necessary to trust the Coq proof assistant's kernel. Coq is a proof assistant which handles mathematical assertions, mechanically checks proofs of these assertions, helps to find formal proofs, and extracts a certified program from the constructive proof of its formal specification. ...

There are also efficient algorithms to determine whether 1 or 2 colors are enough to color a map. Determining whether 3 colors suffice is, however, NP-complete, and so unlikely to have a fast solution. Determining whether a general (possibly non-planar) graph can be 4-colored is also NP-complete. In complexity theory, the NP-complete problems are the most difficult problems in NP, in the sense that they are the ones most likely not to be in P. The reason is that if you could find a way to solve an NP-complete problem quickly, then you could use...

Not for mapmakers

Although the four color theorem was discovered in the process of coloring a real map, it finds no application in practical cartography. According to Kenneth May, a mathematical historian who studied a sample of atlases in the Library of Congress, there is no tendency to minimize the number of colors used. Many maps use color for things other than political regions. Most maps use more than four colors, and when only four colors are used, usually the minimum number of colors actually needed is less than four. Mapmaker redirects here. ...

On most actual maps there are lakes, which must all be in the same color. This is then additional to whatever colors are required for political regions. If the lakes are counted as a single region, the theorem does not apply. It can be applied to the map's land areas alone by considering the lakes as not belonging to the map regions, but on actual maps several non-contiguous map regions may furthermore belong to a single non-connected political region and require the same color (see below), so then again the theorem does not apply. This article or section does not cite any references or sources. ... In mathematics and computer science the connectivity of graphs is one of the basic concepts of graph theory. ...

Textbooks on cartography and the history of cartography do not mention the four color theorem, even though map coloring is a subject of discussion. Generally, mapmakers say they are more concerned about coloring political maps in a balanced fashion, so that no single color dominates. Whether they use four, five, or more colors is not a primary concern. Cartography or mapmaking (in Greek chartis = map and graphein = write) has been an integral part of the human story for a long time (maybe 8,000 years - nobody knows exactly, but longer than written words). ...

Formal statement in graph theory

To formally state the theorem, it is easiest to rephrase it in graph theory. It then 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 "every planar graph is four-colorable" for short. Here, every region of the map is replaced by a vertex of the graph, and two vertices are connected by an edge if and only if the two regions share a border segment (not just a corner). A pictorial representation of a graph In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. ... This article just presents the basic definitions. ... In graph theory, a planar graph is a graph that can be drawn so that no edges intersect (or that can be embedded) in the plane. ... A 3-coloring suits this graph, but fewer colors would result in adjacent vertices of the same color. ... This article just presents the basic definitions. ... This article does not cite any references or sources. ...

Image File history File links Four_Colour_Planar_Graph. ...

False disproofs

Like many famous open problems of mathematics, the four color theorem has attracted a large number of false proofs and disproofs in its long history. Some, like Kempe's and Tait's mentioned above, stood under public scrutiny for over a decade before they were exposed. But many more, authored by amateurs, were never published at all.

This map has been colored with five colors...	...but it is necessary to change at least four of the ten regions to obtain a coloring with only four colors.

Generally, the simplest "counterexamples" attempt to create one region which touches all other regions. This forces the remaining regions to be colored with only three colors. Because the four color theorem is true, this is always possible; however, because the person drawing the map is focused on the one large region, they fail to notice that the remaining regions can in fact be colored with three colors. Image File history File links 4CT_Non-Counterexample_1. ... Image File history File links 4CT_Non-Counterexample_2. ...

This trick can be generalized: there are many maps where if the colors of some regions are selected beforehand, it becomes impossible to color the remaining regions without exceeding four colors. A casual verifier of the counterexample may not think to change the colors of these regions, so that the counterexample will appear as though it is valid.

Perhaps one effect underlying this common misconception is the fact that the color restriction is not transitive: a region only has to be colored differently from regions it touches directly, not regions touching regions that it touches. If this were the restriction, planar graphs would require arbitrarily large numbers of colors. In grammar, a verb is transitive if it takes an object. ...

Other false disproofs violate the assumptions of the theorem in unexpected ways, such as using a region that consists of multiple disconnected parts, or disallowing regions of the same color from touching at a point.

Generalizations

By joining the single arrows together and the double arrows together, one obtains a torus with seven mutually touching regions; therefore seven colors are necessary

This construction shows the torus divided into the maximum of seven regions, every one of which touches every other.

One can also consider the coloring problem on surfaces other than the plane. The problem on the sphere is equivalent to that on the plane. For closed (orientable or non-orientable) surfaces with positive genus, the maximum number p of colors needed depends on the surface's Euler characteristic χ according to the formula Image File history File links Torus_with_seven_colours. ... Image File history File links Torus_with_seven_colours. ... In geometry, a torus (pl. ... Image File history File links No higher resolution available. ... Image File history File links No higher resolution available. ... Two intersecting planes in three-dimensional space In mathematics, a plane is a two-dimensional manifold or surface that is perfectly flat. ... A sphere is a perfectly symmetrical geometrical object. ... In mathematics, the genus has few different meanings Topology The genus of a connected, oriented surface is an integer representing the maximum number of cuttings along closed simple curves without rendering the resultant manifold disconnected. ... It has been suggested that Vertex/Face/Edge relation in a convex polyhedron be merged into this article or section. ...

,

where the outermost brackets denote the floor function. The only exception to the formula is the Klein bottle, which has Euler characteristic 0 and requires 6 colors. This was initially known as the Heawood conjecture and proved as The Map Color Theorem by Gerhard Ringel and J. T. W. Youngs in 1968. The floor and fractional part functions In mathematics, the floor function of a real number x, denoted or floor(x), is the largest integer less than or equal to x (formally, ). For example, floor(2. ... The Klein bottle immersed in three-dimensional space. ... The Heawood conjecture in graph theory was an expected formula to give the correct upper bound for the number of colors which are sufficient for graph coloring on a surface of a given genus. ... This article or section does not adequately cite its references or sources. ...

Alternatively, for an orientable surface the formula can be given in terms of the genus of a surface, g: This article or section should be merged with Orientable manifold. ... In mathematics, the genus has few different meanings Topology The genus of a connected, oriented surface is an integer representing the maximum number of cuttings along closed simple curves without rendering the resultant manifold disconnected. ...

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. In geometry, a torus (pl. ...

Non-contiguous regions

Example of a map with non-contiguous regions

In the real world, not all countries are contiguous (e.g. Alaska as part of the United States, Nakhchivan as part of Azerbaijan, and Kaliningrad as part of Russia). If the chosen coloring scheme requires that the territory of a particular country must be the same color, four colors may not be sufficient. For instance, consider a simplified map: Image File history File links Azerbaijan-CIA_WFB_Map. ... Image File history File links Azerbaijan-CIA_WFB_Map. ... This cites very few or no references or sources. ... Official language(s) English[1] Spoken language(s) English 85. ... Map of Azerbaijan, showing Naxçıvan to the bottom-left Nakhchivan Autonomous Republic (or Naxçıvan Muxtar Respublikası) is an exclave of Azerbaijan. ... Kaliningrad (Russian: ; Lithuanian: Karaliaučius; German  , Polish: Królewiec; briefly Russified as Kyonigsberg), is a seaport and the administrative center of Kaliningrad Oblast, the Russian exclave between Poland and Lithuania on the Baltic Sea. ...

In this map, the two regions labeled A belong to the same country, and must be the same color. This map then requires five colors, since the two A regions together are contiguous with four other regions, each of which is contiguous with all the others. If A consisted of three regions, six or more colors might be required; one can construct maps that require an arbitrarily high number of colors. Image File history File links 4CT_Inadequacy_Example. ...

See also

• Graph coloring
• Graph theory
• Topology
• WikiBooks:Amateur's guide to proving the four color theorem

A 3-coloring suits this graph, but fewer colors would result in adjacent vertices of the same color. ... A pictorial representation of a graph In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. ... A Möbius strip, an object with only one surface and one edge; such shapes are an object of study in topology. ...

References

1. ^ Arthur Cayley, "On the colourings of maps.", Proc. Royal Geographical Society 1, 259-261, 1879.

• Allaire, F. "Another proof of the four colour theorem—Part I", Proceedings, 7th Manitoba Conference on Numerical Mathematics and Computing, Congr. Numer. 20, 1977, 3–72.
• Appel, Kenneth & Haken, Wolfgang & Koch, John, Every Planar map is Four Colorable, Illinois: Journal of Mathematics: vol.21: pp.439-567, December 1977.
• Appel, Kenneth & Haken, Wolfgang, Solution of the Four Color Map Problem, Scientific American, vol.237 no.4: pp.108-121, October 1977.
• Appel, Kenneth & Haken, Wolfgang, Every Planar Map is Four-Colorable. Providence, RI: American Mathematical Society, 1989.
• Gonthier, Georges, A computer-checked proof of the Four Colour Theorem, unpublished.
• O'Connor and Robertson, The Four Colour Theorem, at the MacTutor archive, 1996.
• Ringel, G. and Youngs, J. W. T. "Solution of the Heawood Map-Coloring Problem." Proc. Nat. Acad. Sci. USA 60, 438-445, 1968.
• Robertson, Neil; Sanders, Daniel; Seymour, Paul; and Thomas, Robin, Efficiently four-coloring planar graphs, New York: ACM Press, 1996.
• Saaty and Kainen, The Four Color Problem: Assaults and Conquest (ISBN 0-486-65092-8)
• Thomas, Robin, An Update on the Four-Color Theorem (PDF File), Notices of the American Mathematical Society, Volume 45, number 7 (August 1998)
• Thomas, Robin, The Four Color Theorem, http://www.math.gatech.edu/~thomas/FC/fourcolor.html
• Wilson, Robin, Four Colours Suffice, London: Penguin Books Ltd, 2002.