Related Searches

figure be

Four color theorem

[fawr-kuhl-er, fohr-]

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. Each region must be contiguous: that is, it may not have exclaves like some real countries such as Angola, Azerbaijan, Italy, the United States, or Russia.

It is often the case that using only three colors is inadequate. This applies already to a map with one region surrounded by three other regions (although 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 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 infeasible for a human to verify by hand (see computer-assisted proof). Ultimately, in order to believe the proof, one also has to have the belief (which can be justified or not) that the proof assistant software works as intended and that there were no other errors - such as in the functioning of the hardware - that corrupted the output. The proof is also considered inelegant.


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's brother, Fredrick, was a student of Augustus De Morgan at University College. Francis inquired with Fredrick regarding it, who then took it to De Morgan. (Fredrick Guthrie graduated later in 1852, and later became a professor of mathematics in South Africa). According to De Morgan:

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 colored - 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, who in turn credits the conjecture to De Morgan.

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 was not 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.

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.

Significant results were produced by Croatian mathematician Danilo Blanuša in the 1940s by finding an original snark. In 1943, Hugo Hadwiger formulated the Hadwiger conjecture, a far-reaching generalization of the four-color problem that still remains unsolved.

During the 1960s and 1970s German mathematician Heinrich Heesch developed methods of applying the computer in searching for a proof.

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 A. Koch.

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.

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. Sanders, Paul Seymour, and Robin Thomas created a quadratic time algorithm, improving on a quartic algorithm based on Appel and Haken’s proof. This new proof is similar to Appel and Haken's but more efficient because it reduced the complexity of the problem and required checking only 633 reducible configurations. Both the unavoidability and reducibility parts of this new proof must be executed by computer and are impractical to check by hand.

In 1980, George Spencer-Brown deposited his purported proof of the four color map theorem at the Royal Society. The validity of this proof, which makes up Appendix 5 of the German translation of his book "Laws of Form" (Lübeck 1997), is generally doubted.

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 kernel.

There are also efficient algorithms to determine whether 1 or 2 colors suffice to color a map. Determining whether 3 colors suffice is, however, NP-complete, and so a fast algorithm is unlikely. Determining whether a general (possibly non-planar) graph can be 4-colored is likewise NP-complete.

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). It is possible to represent a map with polygonal regions directly as a graph, where the edges bordering regions are graph edges and corners are vertices; this is the dual graph of the graph just described.

Summary of proof ideas

The following discussion is a summary based on Appel and Haken's Every Planar Map is Four Colorable.

Although flawed, Kempe's original purported proof of the four color theorem provided some of the basic tools later used to prove it. The explanation here is reworded in terms of the modern graph theory formulation above. First, adding edges to a graph cannot decrease its chromatic number; hence, it suffices to consider maximal planar graphs, also known as triangular graphs, where every face (including the infinite outer face) is bounded by three edges. Suppose v, e, and f are the number of vertices, edges, and faces. Since each edge is shared by two faces, 2e = 3f which together with Euler's formula ve + f = 2 can be used to show 6v − 2e = 12. Now, if vn is the number of vertices of degree n and D is the maximum degree,

6v - 2e = 6sum_{i=1}^D v_i - sum_{i=1}^D iv_i = sum_{i=1}^D (6 - i)v_i = 12.







Each vertex is assigned an initial charge of 6-deg(v); then these charges are systematically redistributed among nearby vertices without modifying their sum according to a deterministic discharging procedure. Their sum will still be positive; thus, a complete enumeration of all possible configurations with positive charge is an unavoidable set. As long as some member of the unavoidable set has cannot be successfully reduced, the discharging procedure is modified to eliminate it (while introducing other configurations). Appel and Haken's final discharging procedure was extremely complex and, together with a description of the resulting unavoidable configuration set, filled a 400-page volume, but the configurations it generated could all be mechanically reduced. Verifying the volume describing the unavoidable configuration set itself was done by peer review over a period of several years.


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.





One can also consider the coloring problem on surfaces other than the plane. The problem on the sphere or cylinder 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

p=leftlfloorfrac{7 + sqrt{49 - 24 chi}}{2}rightrfloor,
where the outermost brackets denote the floor function. The only exception to the formula is the Klein bottle, which has Euler characteristic 0 (hence the formula gives p = 7) and requires 6 colors. This was initially known as the Heawood conjecture and proven by Gerhard Ringel and J. T. W. Youngs in 1968.


p=leftlfloorfrac{7 + sqrt{1 + 48g }}{2}rightrfloor.


A Möbius strip also requires six colors.

There is no useful extension of the coloring problem to three-dimensional solid regions. It is trivial to construct a set of n flexible rods, for example, such that every rod touches every other rod. The set would then require n colors, or n+1 if you consider the empty space that also touches every rod. n can be taken to be any integer, as large as desired.

Not for mapmakers

Although the four color theorem was discovered in the process of coloring a real map, it is not useful in practical cartography. The four color theorem only applies given free choice of colours for all regions, a condition that can not always be met, as cartographers color political units (sometimes groups of non-contiguous regions) rather than each region individually. It also allows regions which meet only at points to share the same color, which would cause unnecessary ambiguity for practical maps. Also, if bodies of water are included in the coloring, land regions might be forced to be colored the same as water regions, and noncontiguous water regions might have to be colored differently, which would be confusing.

Mapmakers may also be subject to external constraints. For example, the red/pink color was traditionally reserved for the British Empire in a British world map.

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 fewer than four.

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.

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). Because the territory of a particular country must be the same color, four colors may not be sufficient. For instance, consider a simplified map:

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.

See also



  • 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,
  • FTP resources:
  • Wilson, Robin, Four Colours Suffice, London: Penguin Books Ltd, 2002.

Search another word or see figure beon Dictionary | Thesaurus |Spanish
Copyright © 2013, LLC. All rights reserved.
  • Please Login or Sign Up to use the Recent Searches feature