![Four Colour Map Example](https://upload.wikimedia.org/wikipedia/commons/8/8a/Four_Colour_Map_Example.svg)
![Map of United States accessible colors shown](https://upload.wikimedia.org/wikipedia/commons/b/b1/Map_of_United_States_accessible_colors_shown.svg)
In
mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern 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 curve segment, not merely a corner where three or more regions meet. It was the first major
theorem
In mathematics, a theorem is a statement that has been proved, or can be proved. The ''proof'' of a theorem is a logical argument that uses the inference rules of a deductive system to establish that the theorem is a logical consequence of th ...
to be
proved using a computer. Initially, this proof was not accepted by all mathematicians because the
computer-assisted proof
A computer-assisted proof is a mathematical proof that has been at least partially generated by computer.
Most computer-aided proofs to date have been implementations of large proofs-by-exhaustion of a mathematical theorem. The idea is to use a ...
was
infeasible for a human to check by hand. The proof has gained wide acceptance since then, although some doubters remain.
The four color theorem was proved in 1976 by
Kenneth Appel
Kenneth Ira Appel (October 8, 1932 – April 19, 2013) was an American 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-c ...
and
Wolfgang Haken
Wolfgang Haken (June 21, 1928 – October 2, 2022) was a German American mathematician who specialized in topology, in particular 3-manifolds.
Biography
Haken was born in Berlin, Germany. His father was Werner Haken, a physicist who had Max ...
after many false proofs and counterexamples (unlike the
five color theorem
The five color theorem is a result from graph theory that given a plane separated into regions, such as a political map of the countries of the world, the regions may be colored using no more than five colors in such a way that no two adjacent regi ...
, proved in the 1800s, which states that five colors are enough to color a map). To dispel any remaining doubts 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. In 2005, the theorem was also proved by
Georges Gonthier
Georges Gonthier is a Canadian computer scientist and one of the leading practitioners in formal mathematics. He led the formalization of the four color theorem and Feit–Thompson proof of the odd-order theorem. (Both were written using the ...
with general-purpose
theorem-proving software.
Precise formulation of the theorem
In graph-theoretic terms, the theorem states that for
loopless planar graph
In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cross ...
, its
chromatic number
In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices o ...
is
.
The intuitive statement of the four color theorem – "given any separation of a plane into contiguous regions, the regions can be colored using at most four colors so that no two adjacent regions have the same color" – needs to be interpreted appropriately to be correct.
First, regions are adjacent if they share a boundary segment; two regions that share only isolated boundary points are not considered adjacent. Second, bizarre regions, such as those with finite area but infinitely long perimeter, are not allowed; maps with such regions can require more than four colors. (To be safe, we can restrict to regions whose boundaries consist of finitely many straight line segments. It is allowed that a region entirely surround one or more other regions.) Note that the notion of "contiguous region" (technically:
connected
Connected may refer to:
Film and television
* ''Connected'' (2008 film), a Hong Kong remake of the American movie ''Cellular''
* '' Connected: An Autoblogography About Love, Death & Technology'', a 2011 documentary film
* ''Connected'' (2015 TV ...
open
Open or OPEN may refer to:
Music
* Open (band), Australian pop/rock band
* The Open (band), English indie rock band
* ''Open'' (Blues Image album), 1969
* ''Open'' (Gotthard album), 1999
* ''Open'' (Cowboy Junkies album), 2001
* ''Open'' (YF ...
subset of the plane) is not the same as that of a "country" on regular maps, since countries need not be contiguous (e.g., the
Cabinda Province
Cabinda (formerly called Portuguese Congo, kg, Kabinda) is an exclave and province of Angola in Africa, a status that has been disputed by several political organizations in the territory. The capital city is also called Cabinda, known locall ...
as part of
Angola
, national_anthem = " Angola Avante"()
, image_map =
, map_caption =
, capital = Luanda
, religion =
, religion_year = 2020
, religion_ref =
, coordina ...
,
Nakhchivan as part of
Azerbaijan
Azerbaijan (, ; az, Azərbaycan ), officially the Republic of Azerbaijan, , also sometimes officially called the Azerbaijan Republic is a transcontinental country located at the boundary of Eastern Europe and Western Asia. It is a part of th ...
,
Kaliningrad
Kaliningrad ( ; rus, Калининград, p=kəlʲɪnʲɪnˈɡrat, links=y), until 1946 known as Königsberg (; rus, Кёнигсберг, Kyonigsberg, ˈkʲɵnʲɪɡzbɛrk; rus, Короле́вец, Korolevets), is the largest city and ...
as part of Russia, and
Alaska
Alaska ( ; russian: Аляска, Alyaska; ale, Alax̂sxax̂; ; ems, Alas'kaaq; Yup'ik: ''Alaskaq''; tli, Anáaski) is a state located in the Western United States on the northwest extremity of North America. A semi-exclave of the U.S., ...
as part of the
United States
The United States of America (U.S.A. or USA), commonly known as the United States (U.S. or US) or America, is a country primarily located in North America. It consists of 50 states, a federal district, five major unincorporated territorie ...
are not contiguous). If we required the entire territory of a country to receive the same color, then four colors are not always sufficient. For instance, consider a simplified map:
![4CT Inadequacy Example](https://upload.wikimedia.org/wikipedia/commons/b/b5/4CT_Inadequacy_Example.svg)
In this map, the two regions labeled ''A'' belong to the same country. If we wanted those regions to receive the same color, then five colors would be required, since the two ''A'' regions together are adjacent to four other regions, each of which is adjacent to all the others. Forcing two separate regions to have the same color can be modelled by adding a 'handle' joining them outside the plane.
![4CT Inadequacy Explanation](https://upload.wikimedia.org/wikipedia/commons/b/b8/4CT_Inadequacy_Explanation.svg)
Such construction makes the problem equivalent to coloring a map on a
torus
In geometry, a torus (plural tori, colloquially donut or doughnut) is a surface of revolution generated by revolving a circle in three-dimensional space about an axis that is coplanar with the circle.
If the axis of revolution does not tou ...
(a surface of
genus
Genus ( plural genera ) is a taxonomic rank used in the biological classification of extant taxon, living and fossil organisms as well as Virus classification#ICTV classification, viruses. In the hierarchy of biological classification, genus com ...
1), which requires up to 7 colors for an arbitrary map.
A similar construction also applies if a single color is used for multiple disjoint areas, as for bodies of water on real maps, or there are more countries with disjoint territories. In such cases more colors might be required with a growing genus of a resulting surface. (See the section
Generalizations
A generalization is a form of abstraction whereby common properties of specific instances are formulated as general concepts or claims. Generalizations posit the existence of a domain or set of elements, as well as one or more common characteri ...
below.)
![Four Colour Planar Graph](https://upload.wikimedia.org/wikipedia/commons/a/a4/Four_Colour_Planar_Graph.svg)
A simpler statement of the theorem uses
graph theory
In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conne ...
. The set of regions of a map can be represented more abstractly as an
undirected graph
In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called '' v ...
that has a
vertex
Vertex, vertices or vertexes may refer to:
Science and technology Mathematics and computer science
*Vertex (geometry), a point where two or more curves, lines, or edges meet
*Vertex (computer graphics), a data structure that describes the position ...
for each region and an
edge
Edge or EDGE may refer to:
Technology Computing
* Edge computing, a network load-balancing system
* Edge device, an entry point to a computer network
* Adobe Edge, a graphical development application
* Microsoft Edge, a web browser developed by ...
for every pair of regions that share a boundary segment. This graph is
planar
Planar is an adjective meaning "relating to a plane (geometry)".
Planar may also refer to:
Science and technology
* Planar (computer graphics), computer graphics pixel information from several bitplanes
* Planar (transmission line technologies), ...
: it can be drawn in the plane without crossings by placing each vertex at an arbitrarily chosen location within the region to which it corresponds, and by drawing the edges as curves without crossings that lead from one region's vertex, across a shared boundary segment, to an adjacent region's vertex. Conversely any planar graph can be formed from a map in this way. In graph-theoretic terminology, the four-color theorem 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 for short:
:Every planar graph is
four-colorable.
History
Early proof attempts
![DeMorganFourColour](https://upload.wikimedia.org/wikipedia/commons/7/72/DeMorganFourColour.png)
As far as is known, the conjecture was first proposed on October 23, 1852,
[Donald MacKenzie, ''Mechanizing Proof: Computing, Risk, and Trust'' (MIT Press, 2004) p103] when
Francis Guthrie
Francis Guthrie (born 22 January 1831 in London; d. 19 October 1899 in Claremont, Cape Town) was a South African mathematician and botanist who first posed the Four Colour Problem in 1852. He studied mathematics under Augustus De Morgan, and ...
, while trying to color the map of counties of England, noticed that only four different colors were needed. At the time, Guthrie's brother,
Frederick Frederick may refer to:
People
* Frederick (given name), the name
Nobility
Anhalt-Harzgerode
*Frederick, Prince of Anhalt-Harzgerode (1613–1670)
Austria
* Frederick I, Duke of Austria (Babenberg), Duke of Austria from 1195 to 1198
* Frederi ...
, was a student of
Augustus De Morgan (the former advisor of Francis) at
University College London
, mottoeng = Let all come who by merit deserve the most reward
, established =
, type = Public research university
, endowment = £143 million (2020)
, budget = ...
. Francis inquired with Frederick regarding it, who then took it to De Morgan (Francis Guthrie graduated later in 1852, and later became a professor of mathematics in South Africa). According to De Morgan:
"A student of mine uthrieasked me to day 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 any how divided and the compartments differently colored so that figures with any portion of common boundary ''line'' are differently colored—four colors may be wanted but not more—the following is his case in which four colors ''are'' wanted. Query cannot a necessity for five or more be invented…"
"F.G.", perhaps one of the two Guthries, published the question in ''
The Athenaeum'' in 1854, and De Morgan posed the question again in the same magazine in 1860.
Another early published reference by in turn credits the conjecture to De Morgan.
There were several early failed attempts at proving the theorem. De Morgan believed that it followed from a simple fact about four regions, though he didn't believe that fact could be derived from more elementary facts.
This arises in the following way. We never need four colors in a neighborhood unless there be four counties, each of which has boundary lines in common with each of the other three. Such a thing cannot happen with four areas unless one or more of them be inclosed by the rest; and the color used for the inclosed county is thus set free to go on with. Now this principle, that four areas cannot each have common boundary with all the other three without inclosure, is not, we fully believe, capable of demonstration upon anything more evident and more elementary; it must stand as a postulate.
One proposed proof was given by
Alfred Kempe
Sir Alfred Bray Kempe FRS (6 July 1849 – 21 April 1922) was a mathematician best known for his work on linkages and the four colour theorem.
Biography
Kempe was the son of the Rector of St James's Church, Piccadilly, the Rev. John Edward K ...
in 1879, which was widely acclaimed;
W. W. Rouse Ball
Walter William Rouse Ball (14 August 1850 – 4 April 1925), known as W. W. Rouse Ball, was a British mathematician, lawyer, and fellow at Trinity College, Cambridge, from 1878 to 1905. He was also a keen amateur magician, and the founding ...
(1960) ''The Four Color Theorem'', in Mathematical Recreations and Essays, Macmillan, New York, pp 222–232. another was given by
Peter Guthrie Tait
Peter Guthrie Tait FRSE (28 April 1831 – 4 July 1901) was a Scottish mathematical physicist and early pioneer in thermodynamics. He is best known for the mathematical physics textbook '' Treatise on Natural Philosophy'', which he co-wrote wi ...
in 1880. It was not until 1890 that Kempe's proof was shown incorrect by
Percy Heawood
Percy John Heawood (8 September 1861 – 24 January 1955) was a British mathematician, who concentrated on graph colouring.
Life
He was the son of the Rev. John Richard Heawood of Newport, Shropshire, and his wife Emily Heath, daughter of the ...
, and in 1891, Tait's proof was shown incorrect by
Julius Petersen
Julius Peter Christian Petersen (16 June 1839, Sorø, West Zealand – 5 August 1910, Copenhagen) was a Danish mathematician. His contributions to the field of mathematics led to the birth of graph theory.
Biography
Petersen's interests i ...
—each false proof stood unchallenged for 11 years.
In 1890, in addition to exposing the flaw in Kempe's proof, Heawood proved the
five color theorem
The five color theorem is a result from graph theory that given a plane separated into regions, such as a political map of the countries of the world, the regions may be colored using no more than five colors in such a way that no two adjacent regi ...
and generalized the four color conjecture to surfaces of arbitrary genus.
Tait, in 1880, showed that the four color theorem is equivalent to the statement that a certain type of graph (called a
snark
Snark may refer to:
Fictional creatures
* Snark (Lewis Carroll), a fictional animal species in Lewis Carroll's ''The Hunting of the Snark'' (1876)
* Zn'rx, a race of fictional aliens in Marvel Comics publications, commonly referred to as "Snark ...
in modern terminology) must be non-
planar
Planar is an adjective meaning "relating to a plane (geometry)".
Planar may also refer to:
Science and technology
* Planar (computer graphics), computer graphics pixel information from several bitplanes
* Planar (transmission line technologies), ...
.
In 1943,
Hugo Hadwiger
Hugo Hadwiger (23 December 1908 in Karlsruhe, Germany – 29 October 1981 in Bern, Switzerland) was a Swiss mathematician, known for his work in geometry, combinatorics, and cryptography.
Biography
Although born in Karlsruhe, Germany, Hadwige ...
formulated the
Hadwiger conjecture There are several conjectures known as the Hadwiger conjecture or Hadwiger's conjecture. They include:
* Hadwiger conjecture (graph theory), a relationship between the number of colors needed by a given graph and the size of its largest clique mino ...
, a far-reaching generalization of the four-color problem that still remains unsolved.
Proof by computer
During the 1960s and 1970s, German mathematician
Heinrich Heesch
Heinrich Heesch (June 25, 1906 – July 26, 1995) was a German mathematician. He was born in Kiel and died in Hanover.
In Göttingen he worked on Group theory. In 1933 Heesch witnessed the National Socialist purges of university staff. Not wi ...
developed methods of using computers to search for a proof. Notably he was the first to use
discharging for proving the theorem, which turned out to be important in the unavoidability portion of the subsequent Appel–Haken proof. He also expanded on the concept of reducibility and, along with Ken Durre, developed a computer test for it. Unfortunately, at this critical juncture, he was unable to procure the necessary supercomputer time to continue his work.
Others took up his methods, including his computer-assisted approach. While other teams of mathematicians were racing to complete proofs,
Kenneth Appel
Kenneth Ira Appel (October 8, 1932 – April 19, 2013) was an American 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-c ...
and
Wolfgang Haken
Wolfgang Haken (June 21, 1928 – October 2, 2022) was a German American mathematician who specialized in topology, in particular 3-manifolds.
Biography
Haken was born in Berlin, Germany. His father was Werner Haken, a physicist who had Max ...
at the
University of Illinois
The University of Illinois Urbana-Champaign (U of I, Illinois, University of Illinois, or UIUC) is a public land-grant research university in Illinois in the twin cities of Champaign and Urbana. It is the flagship institution of the University ...
announced, on June 21, 1976, that they had proved the theorem. 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'' is a set of configurations such that every map that satisfies some necessary conditions for being a minimal non-4-colorable
triangulation
In trigonometry and geometry, triangulation is the process of determining the location of a point by forming triangles to the point from known points.
Applications
In surveying
Specifically in surveying, triangulation involves only angle me ...
(such as having minimum degree 5) must have at least one configuration from this set.
# A ''reducible configuration'' is an arrangement of countries that cannot occur in a minimal counterexample. If a map contains a reducible configuration, the map can be reduced to a smaller map. This smaller map has the condition that if it can be colored with four colors, this also applies to the original map. This implies that if the original map cannot be colored with four colors the smaller map cannot either and so the original map is not minimal.
Using mathematical rules and procedures based on properties of reducible configurations, 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,834 reducible configurations (later reduced to 1,482) which had to be checked one by one by computer and took over a thousand hours. This reducibility part of the work was independently double checked with different programs and computers. However, the unavoidability part of the proof was verified in over 400 pages of
microfiche
Microforms are scaled-down reproductions of documents, typically either films or paper, made for the purposes of transmission, storage, reading, and printing. Microform images are commonly reduced to about 4% or of the original document size. F ...
, which had to be checked by hand with the assistance of Haken's daughter
Dorothea Blostein
Dorothea Blostein (' Haken) is a Canadian computer scientist who works as a professor of computer science at Queen's University at Kingston, Queen's University. She has published well-cited publications on computer vision, image analysis, and graph ...
.
Appel and Haken's announcement was widely reported by the news media around the world, and the math department at the
University of Illinois
The University of Illinois Urbana-Champaign (U of I, Illinois, University of Illinois, or UIUC) is a public land-grant research university in Illinois in the twin cities of Champaign and Urbana. It is the flagship institution of the University ...
used a postmark stating "Four colors suffice." At the same time the unusual nature of the proof—it was the first major theorem to be proved with extensive computer assistance—and the complexity of the human-verifiable portion aroused considerable controversy .
In the early 1980s, rumors spread of a flaw in the Appel–Haken proof. Ulrich Schmidt at
RWTH Aachen
RWTH Aachen University (), also known as North Rhine-Westphalia Technical University of Aachen, Rhine-Westphalia Technical University of Aachen, Technical University of Aachen, University of Aachen, or ''Rheinisch-Westfälische Technische Hoch ...
had examined Appel and Haken's proof for his master's thesis that was published in 1981 . He had checked about 40% of the unavoidability portion and found a significant error in the discharging procedure . In 1986, Appel and Haken were asked by the editor of ''
Mathematical Intelligencer
''The Mathematical Intelligencer'' is a mathematical journal published by Springer Verlag that aims at a conversational and scholarly tone, rather than the technical and specialist tone more common among academic journals. Volumes are released quar ...
'' to write an article addressing the rumors of flaws in their proof. They replied that the rumors were due to a "misinterpretation of
chmidt'sresults" and obliged with a detailed article . Their
magnum opus
A masterpiece, ''magnum opus'' (), or ''chef-d’œuvre'' (; ; ) in modern use is a creation that has been given much critical praise, especially one that is considered the greatest work of a person's career or a work of outstanding creativity, ...
, ''Every Planar Map is Four-Colorable'', a book claiming a complete and detailed proof (with a microfiche supplement of over 400 pages), appeared in 1989; it explained and corrected the error discovered by Schmidt as well as several further errors found by others .
Simplification and verification
Since the proving of the theorem, efficient algorithms have been found for 4-coloring maps requiring only
O(''n''
2) time, where ''n'' is the number of vertices. In 1996,
Neil Robertson
Neil Robertson (born 11 February 1982) is an Australian professional snooker player who is a former world champion and former world number one. The only Australian to have won a ranking event, he is also the only player from outside the United ...
,
Daniel P. Sanders
Daniel P. Sanders is an American mathematician. He is known for his 1996 efficient proof (algorithm) of proving the Four color theorem (with Neil Robertson, Paul Seymour, and Robin Thomas). He used to be a guest professor of the department of com ...
,
Paul Seymour, and
Robin Thomas
Robin may refer to:
Animals
* Australasian robins, red-breasted songbirds of the family Petroicidae
* Many members of the subfamily Saxicolinae (Old World chats), including:
**European robin (''Erithacus rubecula'')
** Bush-robin
**Forest ro ...
created a
quadratic-time algorithm, improving on a
quartic-time algorithm based on Appel and Haken's proof. This new proof is similar to Appel and Haken's but more efficient because it reduces the complexity of the problem and requires checking only 633 reducible configurations. Both the unavoidability and reducibility parts of this new proof must be executed by a computer and are impractical to check by hand. In 2001, the same authors announced an alternative proof, by proving the
snark
Snark may refer to:
Fictional creatures
* Snark (Lewis Carroll), a fictional animal species in Lewis Carroll's ''The Hunting of the Snark'' (1876)
* Zn'rx, a race of fictional aliens in Marvel Comics publications, commonly referred to as "Snark ...
conjecture. This proof remains unpublished, however.
In 2005,
Benjamin Werner and
Georges Gonthier
Georges Gonthier is a Canadian computer scientist and one of the leading practitioners in formal mathematics. He led the formalization of the four color theorem and Feit–Thompson proof of the odd-order theorem. (Both were written using the ...
formalized a proof of the theorem inside the
Coq
Coq is an interactive theorem prover first released in 1989. It allows for expressing mathematical assertions, mechanically checks proofs of these assertions, helps find formal proofs, and extracts a certified program from the constructive proof ...
proof assistant. This removed the need to trust the various computer programs used to verify particular cases; it is only necessary to trust the Coq kernel.
Summary of proof ideas
The following discussion is a summary based on the introduction to ''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.
Kempe's argument goes as follows. First, if planar regions separated by the graph are not ''
triangulated
In trigonometry and geometry, triangulation is the process of determining the location of a point by forming triangles to the point from known points.
Applications
In surveying
Specifically in surveying, triangulation involves only angle me ...
'', i.e. do not have exactly three edges in their boundaries, we can add edges without introducing new vertices in order to make every region triangular, including the unbounded outer region. If this
triangulated graph is colorable using four colors or fewer, so is the original graph since the same coloring is valid if edges are removed. So it suffices to prove the four color theorem for triangulated graphs to prove it for all planar graphs, and without loss of generality we assume the graph is triangulated.
Suppose ''v'', ''e'', and ''f'' are the number of vertices, edges, and regions (faces). Since each region is triangular and each edge is shared by two regions, we have that 2''e'' = 3''f''. This together with
Euler's formula
Euler's formula, named after Leonhard Euler, is a mathematical formula in complex analysis that establishes the fundamental relationship between the trigonometric functions and the complex exponential function. Euler's formula states that for an ...
, ''v'' − ''e'' + ''f'' = 2, can be used to show that 6''v'' − 2''e'' = 12. Now, the ''degree'' of a vertex is the number of edges abutting it. If ''v''
''n'' is the number of vertices of degree ''n'' and ''D'' is the maximum degree of any vertex,
:
But since 12 > 0 and 6 − ''i'' ≤ 0 for all ''i'' ≥ 6, this demonstrates that there is at least one vertex of degree 5 or less.
If there is a graph requiring 5 colors, then there is a ''minimal'' such graph, where removing any vertex makes it four-colorable. Call this graph ''G''. Then ''G'' cannot have a vertex of degree 3 or less, because if ''d''(''v'') ≤ 3, we can remove ''v'' from ''G'', four-color the smaller graph, then add back ''v'' and extend the four-coloring to it by choosing a color different from its neighbors.
![Kempe Chain](https://upload.wikimedia.org/wikipedia/commons/f/f9/Kempe_Chain.svg)
Kempe also showed correctly that ''G'' can have no vertex of degree 4. As before we remove the vertex ''v'' and four-color the remaining vertices. If all four neighbors of ''v'' are different colors, say red, green, blue, and yellow in clockwise order, we look for an alternating path of vertices colored red and blue joining the red and blue neighbors. Such a path is called a
Kempe chain Kempe may refer to:
* Kempe baronets, a title in the Baronetage of England
* Kempe chain, part of the four-colour theorem
* Kempe Fjord, King Christian X Land, Greenland
* Kempe Glacier, Antarctica
* Kempe Hill, former name of Camp Hill, West Mid ...
. There may be a Kempe chain joining the red and blue neighbors, and there may be a Kempe chain joining the green and yellow neighbors, but not both, since these two paths would necessarily intersect, and the vertex where they intersect cannot be colored. Suppose it is the red and blue neighbors that are not chained together. Explore all vertices attached to the red neighbor by red-blue alternating paths, and then reverse the colors red and blue on all these vertices. The result is still a valid four-coloring, and ''v'' can now be added back and colored red.
This leaves only the case where ''G'' has a vertex of degree 5; but Kempe's argument was flawed for this case. Heawood noticed Kempe's mistake and also observed that if one was satisfied with proving only five colors are needed, one could run through the above argument (changing only that the minimal counterexample requires 6 colors) and use Kempe chains in the degree 5 situation to prove the
five color theorem
The five color theorem is a result from graph theory that given a plane separated into regions, such as a political map of the countries of the world, the regions may be colored using no more than five colors in such a way that no two adjacent regi ...
.
In any case, to deal with this degree 5 vertex case requires a more complicated notion than removing a vertex. Rather the form of the argument is generalized to considering ''configurations'', which are connected subgraphs of ''G'' with the degree of each vertex (in G) specified. For example, the case described in degree 4 vertex situation is the configuration consisting of a single vertex labelled as having degree 4 in ''G''. As above, it suffices to demonstrate that if the configuration is removed and the remaining graph four-colored, then the coloring can be modified in such a way that when the configuration is re-added, the four-coloring can be extended to it as well. A configuration for which this is possible is called a ''reducible configuration''. If at least one of a set of configurations must occur somewhere in G, that set is called ''unavoidable''. The argument above began by giving an unavoidable set of five configurations (a single vertex with degree 1, a single vertex with degree 2, ..., a single vertex with degree 5) and then proceeded to show that the first 4 are reducible; to exhibit an unavoidable set of configurations where every configuration in the set is reducible would prove the theorem.
Because ''G'' is triangular, the degree of each vertex in a configuration is known, and all edges internal to the configuration are known, the number of vertices in ''G'' adjacent to a given configuration is fixed, and they are joined in a cycle. These vertices form the ''ring'' of the configuration; a configuration with ''k'' vertices in its ring is a ''k''-ring configuration, and the configuration together with its ring is called the ''ringed configuration''. As in the simple cases above, one may enumerate all distinct four-colorings of the ring; any coloring that can be extended without modification to a coloring of the configuration is called ''initially good''. For example, the single-vertex configuration above with 3 or less neighbors were initially good. In general, the surrounding graph must be systematically recolored to turn the ring's coloring into a good one, as was done in the case above where there were 4 neighbors; for a general configuration with a larger ring, this requires more complex techniques. Because of the large number of distinct four-colorings of the ring, this is the primary step requiring computer assistance.
Finally, it remains to identify an unavoidable set of configurations amenable to reduction by this procedure. The primary method used to discover such a set is the
method of discharging. The intuitive idea underlying discharging is to consider the planar graph as an electrical network. Initially positive and negative "electrical charge" is distributed amongst the vertices so that the total is positive.
Recall the formula above:
:
Each vertex is assigned an initial charge of 6-deg(''v''). Then one "flows" the charge by systematically redistributing the charge from a vertex to its neighboring vertices according to a set of rules, the ''discharging procedure''. Since charge is preserved, some vertices still have positive charge. The rules restrict the possibilities for configurations of positively charged vertices, so enumerating all such possible configurations gives an unavoidable set.
As long as some member of the unavoidable set is not reducible, 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 be checked mechanically to be reducible. Verifying the volume describing the unavoidable configuration set itself was done by peer review over a period of several years.
A technical detail not discussed here but required to complete the proof is ''
immersion
Immersion may refer to:
The arts
* "Immersion", a 2012 story by Aliette de Bodard
* ''Immersion'', a French comic book series by Léo Quievreux
* ''Immersion'' (album), the third album by Australian group Pendulum
* ''Immersion'' (film), a 2021 ...
reducibility''.
False disproofs
The four color theorem has been notorious for attracting a large number of false proofs and disproofs in its long history. At first, ''
The New York Times
''The New York Times'' (''the Times'', ''NYT'', or the Gray Lady) is a daily newspaper based in New York City with a worldwide readership reported in 2020 to comprise a declining 840,000 paid print subscribers, and a growing 6 million paid ...
'' refused, as a matter of policy, to report on the Appel–Haken proof, fearing that the proof would be shown false like the ones before it . Some alleged proofs, like Kempe's and Tait's mentioned above, stood under public scrutiny for over a decade before they were refuted. But many more, authored by amateurs, were never published at all.
Generally, the simplest, though invalid, 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.
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.
Other false disproofs violate the assumptions of the theorem, such as using a region that consists of multiple disconnected parts, or disallowing regions of the same color from touching at a point.
Three-coloring
![visual_proof_USA_states_map_needs_4_colors](https://upload.wikimedia.org/wikipedia/commons/e/ea/Visual_proof_USA_states_map_needs_4_colors.svg)
While every planar map can be colored with four colors, it is
NP-complete
In computational complexity theory, a problem is NP-complete when:
# it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by tryi ...
in
complexity
Complexity characterises the behaviour of a system or model whose components interaction, interact in multiple ways and follow local rules, leading to nonlinearity, randomness, collective dynamics, hierarchy, and emergence.
The term is generall ...
to decide whether an arbitrary planar map can be colored with just three colors.
A cubic map can be colored with only three colors if and only if each interior region has an even number of neighboring regions.
In the US states map example, landlocked
Missouri
Missouri is a U.S. state, state in the Midwestern United States, Midwestern region of the United States. Ranking List of U.S. states and territories by area, 21st in land area, it is bordered by eight states (tied for the most with Tennessee ...
(MO) has eight neighbors (an even number): it must be differently colored from all of them, but the neighbors can alternate colors, thus this part of the map needs only three colors. However, landlocked
Nevada
Nevada ( ; ) is a U.S. state, state in the Western United States, Western region of the United States. It is bordered by Oregon to the northwest, Idaho to the northeast, California to the west, Arizona to the southeast, and Utah to the east. N ...
(NV) has five neighbors (an odd number): one of the neighbors must be differently colored from it and all the others, thus four colors are needed here.
Generalizations
Infinite graphs
![Torus with seven colours](https://upload.wikimedia.org/wikipedia/commons/5/53/Torus_with_seven_colours.svg)
The four color theorem applies not only to finite planar graphs, but also to
infinite graph
This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges.
Symbols
A
B
...
s that can be drawn without crossings in the plane, and even more generally to infinite graphs (possibly with an uncountable number of vertices) for which every finite subgraph is planar. To prove this, one can combine a proof of the theorem for finite planar graphs with the
De Bruijn–Erdős theorem stating that, if every finite subgraph of an infinite graph is ''k''-colorable, then the whole graph is also ''k''-colorable . This can also be seen as an immediate consequence of
Kurt Gödel
Kurt Friedrich Gödel ( , ; April 28, 1906 – January 14, 1978) was a logician, mathematician, and philosopher. Considered along with Aristotle and Gottlob Frege to be one of the most significant logicians in history, Gödel had an imme ...
's
compactness theorem
In mathematical logic, the compactness theorem states that a set of first-order sentences has a model if and only if every finite subset of it has a model. This theorem is an important tool in model theory, as it provides a useful (but generally no ...
for
first-order logic
First-order logic—also known as predicate logic, quantificational logic, and first-order predicate calculus—is a collection of formal systems used in mathematics, philosophy, linguistics, and computer science. First-order logic uses quantifie ...
, simply by expressing the colorability of an infinite graph with a set of logical formulae.
Higher surfaces
One can also consider the coloring problem on surfaces other than the plane. The problem on the
sphere
A sphere () is a Geometry, geometrical object that is a solid geometry, three-dimensional analogue to a two-dimensional circle. A sphere is the Locus (mathematics), set of points that are all at the same distance from a given point in three ...
or
cylinder
A cylinder (from ) has traditionally been a three-dimensional solid, one of the most basic of curvilinear geometric shapes. In elementary geometry, it is considered a prism with a circle as its base.
A cylinder may also be defined as an infin ...
is equivalent to that on the plane. For closed (orientable or non-orientable) surfaces with positive
genus
Genus ( plural genera ) is a taxonomic rank used in the biological classification of extant taxon, living and fossil organisms as well as Virus classification#ICTV classification, viruses. In the hierarchy of biological classification, genus com ...
, the maximum number ''p'' of colors needed depends on the surface's
Euler characteristic
In mathematics, and more specifically in algebraic topology and polyhedral combinatorics, the Euler characteristic (or Euler number, or Euler–Poincaré characteristic) is a topological invariant, a number that describes a topological space ...
χ according to the formula
:
where the outermost brackets denote the
floor function
In mathematics and computer science, the floor function is the function that takes as input a real number , and gives as output the greatest integer less than or equal to , denoted or . Similarly, the ceiling function maps to the least int ...
.
Alternatively, for an
orientable
In mathematics, orientability is a property of some topological spaces such as real vector spaces, Euclidean spaces, surfaces, and more generally manifolds that allows a consistent definition of "clockwise" and "counterclockwise". A space is ...
surface the formula can be given in terms of the genus of a surface, ''g'':
::
This formula, the
Heawood conjecture
In graph theory, the Heawood conjecture or Ringel–Youngs theorem gives a lower bound for the number of colors that are necessary for graph coloring on a surface of a given genus. For surfaces of genus 0, 1, 2, 3, 4, 5, 6, 7, ..., the required ...
, was proposed by
P. J. Heawood in 1890 and, after contributions by several people, proved by
Gerhard Ringel
Gerhard Ringel (October 28, 1919 in Kollnbrunn, Austria – June 24, 2008 in Santa Cruz, California) was a German mathematician. He was one of the pioneers in graph theory and contributed significantly to the proof of the Heawood conjecture (now ...
and
J. W. T. Youngs in 1968. The only exception to the formula is the
Klein bottle
In topology, a branch of mathematics, the Klein bottle () is an example of a non-orientable surface; it is a two-dimensional manifold against which a system for determining a normal vector cannot be consistently defined. Informally, it is a o ...
, which has Euler characteristic 0 (hence the formula gives p = 7) but requires only 6 colors, as shown by
Philip Franklin
Philip Franklin (October 5, 1898 – January 27, 1965) was an American mathematician and professor whose work was primarily focused in analysis.
Dr. Franklin received a B.S. in 1918 from City College of New York (who later awarded him ...
in 1934.
For example, the
torus
In geometry, a torus (plural tori, colloquially donut or doughnut) is a surface of revolution generated by revolving a circle in three-dimensional space about an axis that is coplanar with the circle.
If the axis of revolution does not tou ...
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. This upper bound of 7 is sharp: certain
toroidal polyhedra
In geometry, a toroidal polyhedron is a polyhedron which is also a toroid (a -holed torus), having a topological genus () of 1 or greater. Notable examples include the Császár and Szilassi polyhedra.
Variations in definition
Toroidal polyhedr ...
such as the
Szilassi polyhedron
In geometry, the Szilassi polyhedron is a nonconvex polyhedron, topologically a torus, with seven hexagonal faces.
Coloring and symmetry
The 14 vertices and 21 edges of the Szilassi polyhedron form an embedding of the Heawood graph onto the surf ...
require seven colors.
A
Möbius strip
In mathematics, a Möbius strip, Möbius band, or Möbius loop is a surface that can be formed by attaching the ends of a strip of paper together with a half-twist. As a mathematical object, it was discovered by Johann Benedict Listing and Augu ...
requires six colors as do
1-planar graph
In topological graph theory, a 1-planar graph is a graph that can be drawn in the Euclidean plane in such a way that each edge has at most one crossing point, where it crosses a single additional edge. If a 1-planar graph, one of the most natural ...
s (graphs drawn with at most one simple crossing per edge) . If both the vertices and the faces of a planar graph are colored, in such a way that no two adjacent vertices, faces, or vertex-face pair have the same color, then again at most six colors are needed .
7_colour_torus.svg, A radially symmetric 7-colored torus – regions of the same colour wrap around along dotted lines
Tietze_genus_2_colouring.svg, An 8-coloured double torus (genus-two surface) – bubbles denotes unique combination of two regions
Klein_bottle_colouring.svg, A 6-colored Klein bottle
In topology, a branch of mathematics, the Klein bottle () is an example of a non-orientable surface; it is a two-dimensional manifold against which a system for determining a normal vector cannot be consistently defined. Informally, it is a o ...
Tietze_Moebius.svg, Tietze's subdivision of a Möbius strip
In mathematics, a Möbius strip, Möbius band, or Möbius loop is a surface that can be formed by attaching the ends of a strip of paper together with a half-twist. As a mathematical object, it was discovered by Johann Benedict Listing and Augu ...
into six mutually adjacent regions, requiring six colors. The vertices and edges of the subdivision form an embedding of Tietze's graph
In the mathematical field of graph theory, Tietze's graph is an undirected cubic graph with 12 vertices and 18 edges.
It is named after Heinrich Franz Friedrich Tietze, who showed in 1910 that the Möbius strip can be subdivided into six regi ...
onto the strip.
Szilassi polyhedron 3D model.svg, link=, Interactive Szilassi polyhedron
In geometry, the Szilassi polyhedron is a nonconvex polyhedron, topologically a torus, with seven hexagonal faces.
Coloring and symmetry
The 14 vertices and 21 edges of the Szilassi polyhedron form an embedding of the Heawood graph onto the surf ...
model with each of 7 faces adjacent to every other – in the SVG image,move the mouse to rotate it
visual_proof_mutually_touching_solids.svg, Proof without words
In mathematics, a proof without words (or visual proof) is an illustration of an identity or mathematical statement which can be demonstrated as self-evident by a diagram without any accompanying explanatory text. Such proofs can be considered mor ...
that the number of colours needed is unbounded in three or more dimensions
Solid regions
There is no obvious extension of the coloring result to three-dimensional solid regions. By using a set of ''n'' flexible rods, one can arrange that every rod touches every other rod. The set would then require ''n'' colors, or ''n''+1 including the empty space that also touches every rod. The number ''n'' can be taken to be any integer, as large as desired. Such examples were known to Fredrick Guthrie in 1880 . Even for axis-parallel
cuboid
In geometry, a cuboid is a hexahedron, a six-faced solid. Its faces are quadrilaterals. Cuboid means "like a cube", in the sense that by adjusting the length of the edges or the angles between edges and faces a cuboid can be transformed into a cub ...
s (considered to be adjacent when two cuboids share a two-dimensional boundary area) an unbounded number of colors may be necessary (; ).
Relation to other areas of mathematics
Dror Bar-Natan
Dror Bar-Natan ( he, דרוֹר בָר-נָתָן; born January 30, 1966) is a professor at the University of Toronto Department of Mathematics, Canada. His main research interests include knot theory, finite type invariants, and Khovanov homology ...
gave a statement concerning
Lie algebras
In mathematics, a Lie algebra (pronounced ) is a vector space \mathfrak g together with an operation called the Lie bracket, an alternating bilinear map \mathfrak g \times \mathfrak g \rightarrow \mathfrak g, that satisfies the Jacobi identi ...
and
Vassiliev invariant
Vasilyev, Vasiliev or Vassiliev or Vassiljev (russian: Васильев), or Vasilyeva or Vasilieva (feminine; russian: link=no, Васильева), is a common Russian surname that is derived from the Russian given name ''Vasiliy'' (equivalent o ...
s which is equivalent to the four color theorem.
Use outside of mathematics
Despite the motivation from
coloring political maps of countries, the theorem is not of particular interest to
cartographers
Cartography (; from grc, χάρτης , "papyrus, sheet of paper, map"; and , "write") is the study and practice of making and using maps. Combining science, aesthetics and technique, cartography builds on the premise that reality (or an im ...
. According to an article by the math historian
Kenneth May
Kenneth O. May (July 8, 1915, in Portland, Oregon – December 1977, in Toronto) was an American mathematician and historian of mathematics, who developed May's theorem.
May was a prime mover behind the International Commission on the History of ...
, "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" . The theorem also does not guarantee the usual cartographic requirement that non-contiguous regions of the same country (such as the exclave
Alaska
Alaska ( ; russian: Аляска, Alyaska; ale, Alax̂sxax̂; ; ems, Alas'kaaq; Yup'ik: ''Alaskaq''; tli, Anáaski) is a state located in the Western United States on the northwest extremity of North America. A semi-exclave of the U.S., ...
and the rest of the
United States
The United States of America (U.S.A. or USA), commonly known as the United States (U.S. or US) or America, is a country primarily located in North America. It consists of 50 states, a federal district, five major unincorporated territorie ...
) be colored identically.
See also
*
Apollonian network
In combinatorial mathematics, an Apollonian network is an undirected graph formed by a process of recursively subdividing a triangle into three smaller triangles. Apollonian networks may equivalently be defined as the planar 3-trees, the maxima ...
*
Five color theorem
The five color theorem is a result from graph theory that given a plane separated into regions, such as a political map of the countries of the world, the regions may be colored using no more than five colors in such a way that no two adjacent regi ...
*
Graph coloring
In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices o ...
*
Grötzsch's theorem
In the mathematical field of graph theory, Grötzsch's theorem is the statement that every triangle-free planar graph can be colored with only three colors. According to the four-color theorem, every graph that can be drawn in the plane without ed ...
:
triangle-free
In the mathematical area of graph theory, a triangle-free graph is an undirected graph in which no three vertices form a triangle of edges. Triangle-free graphs may be equivalently defined as graphs with clique number ≤ 2, graphs with g ...
planar graphs are 3-colorable.
*
Hadwiger–Nelson problem
In geometric graph theory, the Hadwiger–Nelson problem, named after Hugo Hadwiger and Edward Nelson, asks for the minimum number of colors required to color the plane such that no two points at distance 1 from each other have the same color. ...
: how many colors are needed to color the plane so that no two points at unit distance apart have the same color?
Notes
References
*
*
*
*
*
*
*
* .
*
*
*.
*
*
*
*
*
*
*
*
*
*
* .
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
External links
* {{springer, title=Four-colour problem, id=p/f040970
List of generalizations of the four color theoremon
MathOverflow
MathOverflow is a mathematics question-and-answer (Q&A) website, which serves as an online community of mathematicians. It allows users to ask questions, submit answers, and rate both, all while getting merit points for their activities. It is a ...
Computer-assisted proofs
Graph coloring
Planar graphs
Theorems in graph theory