Citizendia

Example of a four-colored map
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. 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. Contiguity is a series of things in continuous connection a grouping of parts in contiguous physical contact Angola, officially the Republic of Angola (República de Angola Pronounced ʁɛˈpublikɐ dɨ ɐ̃ˈgɔlɐ Repubilika ya Ngola is a country in south-central Azerbaijan ( English; Azərbaycan officially the Republic of Azerbaijan (Azərbaycan Respublikası is the largest and most populous country in the South Italy (Italia officially the Italian Republic, (Repubblica Italiana is located on the Italian Peninsula in Southern Europe, and on the two largest The United States of America —commonly referred to as the Russia (Россия Rossiya) or the Russian Federation ( Rossiyskaya Federatsiya) is a transcontinental Country extending

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 five color theorem is a result from Graph theory that given a plane separated into regions such as a political map of the counties of a state the regions may be colored

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). In Mathematics, a theorem is a statement proven on the basis of previously accepted or established statements A computer-assisted proof is a Mathematical proof that has been at least partially generated by computer Ultimately, in order to believe the proof, one also has to have the belief (which can be justified or not) that the compiler works as intended and that the were no other errors - such as in the functioning of the hardware - that corrupted the output. Belief is the psychological state in which an individual holds a Proposition or Premise to be true A compiler is a Computer program (or set of programs that translates text written in a computer language (the source language) into another Hardware is a general term that refers to the physical artifacts of a Technology.

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!"[1]

Contents

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. In Mathematics, a proof is a convincing demonstration (within the accepted standards of the field that some Mathematical statement is necessarily true In Mathematics, a conjecture is a Mathematical statement which appears resourceful but has not been formally proven to be true under the rules of Francis Guthrie (b January 22 1831 in London d October 19 1899 in Claremont Cape Town was a South African mathematician and botanist who first posed the Four England is a Country which is part of the United Kingdom. Its inhabitants account for more than 83% of the total UK population whilst its mainland At the time, Guthrie's brother, Fredrick, was a student of Augustus De Morgan at University College. Augustus De Morgan ( 27 June, 1806 &ndash 18 March, 1871) was a British Mathematician and Logician. University College London ( UCL) is a multi-faculty university institution based in the United Kingdom and a constituent college of the University of London 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). The Republic of South Africa (also known by other official names) is a country located at the southern tip of the continent of 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,[2] 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. In Mathematics, a theorem is a statement proven on the basis of previously accepted or established statements 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. In Mathematics, a proof is a convincing demonstration (within the accepted standards of the field that some Mathematical statement is necessarily true Sir Alfred Bray Kempe DCL FRS (6 July 1849 Kensington, London – 21 April 1922 London) was a Mathematician Peter Guthrie Tait ( April 28, 1831 - July 4, 1901) was a Scottish mathematical physicist, best known for the seminal energy 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. Percy John Heawood ( 8 September, 1861 Newport Shropshire, England - 24 January, 1955 Durham, England Julius Peter Christian Petersen ( June 16, 1839, Sorø on Zealand &ndash 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. Kuratowski's and Wagner's theorems The Polish mathematician Kazimierz Kuratowski provided a characterization of planar graphs in terms of Forbidden The five color theorem is a result from Graph theory that given a plane separated into regions such as a political map of the counties of a state the regions may be colored

Significant results were produced by Croatian mathematician Danilo Blanuša in the 1940s by finding an original snark. Croatia (Hrvatska ˈxȓvatska officially the Republic of Croatia ( Republika Hrvatska) is a southern Central European country at the crossroads between Danilo Blanuša ( December 7 1903 &ndash August 8 1987) was a Croatian mathematician physicist engineer and a Professor In Graph theory, a snark is a connected bridgeless Cubic graph with Chromatic index equal to 4 In 1943, Hugo Hadwiger formulated the Hadwiger conjecture, a far-reaching generalization of the four-color problem that still remains unsolved. Hugo Hadwiger (1908 &ndash 1981 was a Swiss Mathematician. He is known for Hadwiger's theorem in Integral geometry, and a number of conjectures In Graph theory, the Hadwiger conjecture (or Hadwiger's conjecture) states that if an Undirected graph G requires k or more colors

During the 1960s and 1970s German mathematician Heinrich Heesch developed methods of applying the computer in searching for a proof. Germany, officially the Federal Republic of Germany ( ˈbʊndəsʁepuˌbliːk ˈdɔʏtʃlant is a Country in Central Europe. Heinrich Heesch (June 25 1906 &ndash July 26 1995 was a German Mathematician. A computer is a Machine that manipulates data according to a list of instructions.

It was not until 1976 that the four-color conjecture was finally proven by Kenneth Appel and Wolfgang Haken at the University of Illinois. 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 This article is about the flagship campus For other uses and locations of University of Illinois, see University of Illinois (disambiguation The University of They were assisted in some algorithmic work by John Koch. John Koch (1909-1978 is an American painter One of his works is The Sculptor (1964 an oil on canvas painting

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:

Using mathematical rules and procedures based on properties of reducible configurations (e. g. the method of discharging, rings, Kempe chains, etc. The discharging method is a technique used to prove lemmas in structural Graph theory. ), 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 Continuum Fingerboard is a music performance controller developed by Lippold Haken, a professor of Electrical and Computer Engineering at the University of Illinois 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 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 mathematics big O notation (so called because it uses the symbol O) describes the limiting behavior of a function for very small or very large arguments In 1996, Neil Robertson, Daniel P. Year 1996 ( MCMXCVI) was a Leap year starting on Monday (link will display full 1996 Gregorian calendar) G Neil Robertson is a mathematician working mainly in Topological graph theory, currently a distinguished professor at The Ohio State University. Sanders, Paul Seymour, and Robin Thomas created a quadratic time algorithm, utilizing Edward Belaga's work to improve a quartic algorithm based on Appel and Haken’s proof. Paul D Seymour (born July 26, 1950) is a mathematician working in Discrete mathematics, including Combinatorics, Graph theory Edward Grigorievich Belaga (also Eduard Belaga) (born 22 December 1939) is a Russian mathematician. [3] 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. George Spencer-Brown (born April 2, 1923, Grimsby, Lincolnshire, England) is a Polymath best known as the author of The Royal Society of London for the Improvement of Natural Knowledge, known simply as The Royal Society, is a Learned society for science that was founded in 1660 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. Laws of Form (hereinafter LoF) is a book by G Spencer-Brown, published in 1969 that straddles the boundary between Mathematics and of

In 2004 Benjamin Werner and Georges Gonthier formalized a proof of the theorem inside the Coq proof assistant (Gonthier, n. In Computer science, Coq is a Proof assistant application It allows the expression of mathematical assertions mechanically checks proofs of these assertions 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. In Computational complexity theory, the Complexity class NP-complete (abbreviated NP-C or NPC) is a class of problems having two properties Determining whether a general (possibly non-planar) graph can be 4-colored is likewise NP-complete. In Mathematics and Computer science, a graph is the basic object of study in Graph theory.

Not for mapmakers

Although the four color theorem was discovered in the process of coloring a real map, it is rarely used 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 fewer than four.

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. Contiguity is a series of things in continuous connection a grouping of parts in contiguous physical contact In Mathematics and Computer science, connectivity 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. Cartography or mapmaking (in Greek chartis = map and graphein = write has been an integral part of the human story for a long time (maybe 8000 years 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.

Formal statement in graph theory

To formally state the theorem, it is easiest to rephrase it in graph theory. In Mathematics and Computer science, graph theory is the study of graphs: mathematical structures used to model pairwise relations between objects 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. For other uses see Vertex. In Graph theory, a vertex (plural vertices) or node is the fundamental unit out Kuratowski's and Wagner's theorems The Polish mathematician Kazimierz Kuratowski provided a characterization of planar graphs in terms of Forbidden 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 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). In Mathematics and Computer science, a graph is the basic object of study in Graph theory. ↔ 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. In Mathematics, a dual graph of a given Planar graph G is a graph which has a vertex for each plane region of G, and an edge for each edge

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 v − e + 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 = 6\sum_{i=1}^D v_i - \sum_{i=1}^D iv_i = \sum_{i=1}^D (6 - i)v_i = 12.

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 maximal planar graph requiring 5 colors, then there is a minimal such graph, where removing any vertex makes it four-colorable. Call this graph G. 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 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. 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 there is no simple proof for this case. Instead, 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 the previous paragraph 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 discharging method is a technique used to prove lemmas in structural Graph theory. Recall the formula above:

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

A technical detail not discussed here but required to complete the proof is immersion reducibility.

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.

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. In Mathematics, a Binary relation R over a set X is transitive if whenever an element a is related to an element b If this were the restriction, planar graphs would require arbitrarily large numbers of colors.

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
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.
This construction shows the torus divided into the maximum of seven regions, every one of which touches every other. In Geometry, a torus (pl tori) is a Surface of revolution generated by revolving a Circle in three dimensional space about an axis Coplanar

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. "Globose" redirects here See also Globose nucleus. A sphere (from Greek σφαίρα - sphaira, "globe A cylinder is one of the most basic curvilinear geometric shapes the Surface formed by the points at a fixed distance from a given Straight line, the axis 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=\left\lfloor\frac{7 + \sqrt{49 - 24 \chi}}{2}\right\rfloor,

where the outermost brackets denote the floor function. In Mathematics, genus has a few different but closely related meanings Topology Orientable surface In Mathematics, and more specifically in Algebraic topology and Polyhedral combinatorics, the Euler characteristic is a Topological invariant In Mathematics and Computer science, the floor and ceiling functions map Real numbers to nearby Integers The 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. In Mathematics, the Klein bottle is a certain non- orientable Surface, i This was initially known as the Heawood conjecture and proved as The Map Color Theorem by Gerhard Ringel and J. The Heawood conjecture or Ringel–Youngs theorem in Graph theory gives an Upper bound for the number of colors which are Sufficient for Gerhard Ringel (born October 28, 1919, Kolnbrunn Austria Died June 24 2008 Santa Cruz California is a German Mathematician who earned his Ph T. W. Youngs in 1968.

Alternatively, for an orientable surface the formula can be given in terms of the genus of a surface, g:

p=\left\lfloor\frac{7 + \sqrt{1 + 48g }}{2}\right\rfloor.

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. A surface S in the Euclidean space R 3 is orientable if a two-dimensional figure (for example) cannot be moved around the surface and back In Mathematics, genus has a few different but closely related meanings Topology Orientable surface In Geometry, a torus (pl tori) is a Surface of revolution generated by revolving a Circle in three dimensional space about an axis Coplanar

A Möbius strip also requires six colors. This article is about the mathematical object See Mobius Band (music group for the music group [1]

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.

Non-contiguous regions

Example of a map with 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). Alaska ( Аляска Alyaska) is a state in the United States of America, in the northwest of the North American continent The United States of America —commonly referred to as the The Nakhchivan Autonomous Republic (Naxçıvan Muxtar Respublikası Նախիջևանի Ինքնավար Հանրապետություն Нахичеванская Автономная Azerbaijan ( English; Azərbaycan officially the Republic of Azerbaijan (Azərbaycan Respublikası is the largest and most populous country in the South Kaliningrad (Калининград is a Seaport and the administrative center of Kaliningrad Oblast, the Russian Exclave between Poland Russia (Россия Rossiya) or the Russian Federation ( Rossiyskaya Federatsiya) is a transcontinental Country extending 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:

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

References

  1. ^ Mathematics, Microsoft Encarta Online Encyclopedia, Microsoft Corporation, 2007. In Graph theory the road coloring Theorem, known until recently as the road coloring Conjecture, deals with synchronized Instructions 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 In Mathematics and Computer science, graph theory is the study of graphs: mathematical structures used to model pairwise relations between objects Topology ( Greek topos, "place" and logos, "study" is the branch of Mathematics that studies the properties of
  2. ^ Arthur Cayley, "On the colourings of maps. ", Proc. Royal Geographical Society 1, 259-261, 1879. History Founding members of the Society include Sir John Barrow, Sir John Franklin and Francis Beaufort.
  3. ^ Neil Robertson, Daniel P. Sanders, Paul Seymour, and Robin Thomas. A new proof of the four-colour theorem. Electronic Research Announcements of the American Mathematical Society 2 (1996), pp. 17-25. Online archive
© 2009 citizendia.org; parts available under the terms of GNU Free Documentation License, from http://en.wikipedia.org