Four color theorem - Knowledge (XXG)

1638: 1618: 294:: 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 1595: 39: 1182: 1568: 1808:: "Definitions: A planar map is a set of pairwise disjoint subsets of the plane, called regions. A simple map is one whose regions are connected open sets. Two regions of a map are adjacent if their respective closures have a common point that is not a corner of the map. A point is a corner of a map if and only if it belongs to the closures of at least three regions. Theorem: The regions of any simple planar map can be colored with only four colors, in such a way that any two adjacent regions have different colors." 933:. 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 1747: 1556: 1003:. For example, the single-vertex configuration above with 3 or fewer 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. 1580: 1143: 1134: 579:-time algorithm based on Appel and Haken's proof. The new proof, based on the same ideas, 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 1234: 267: 31: 249: 312: 910: 972:. 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. 493:

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

1727:, "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 964:. 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 944:

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

378:

This arises in the following way. We never need four colours 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 colour used for

1162:

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

444:

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

1158:

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

492:

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

487:

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

193:

would make an arbitrarily large number of regions 'adjacent' to each other at a common corner, and require arbitrarily large number of colors as a result.) Second, bizarre regions, such as those with finite area but infinitely long perimeter, are not allowed; maps with such regions can require more

100:

The Appel–Haken proof proceeds by analyzing a very large number of reducible configurations. This was improved upon in 1997 by Robertson, Sanders, Seymour, and Thomas who have managed to decrease the number of such configurations to 633 – still an extremely long case analysis. In 2005, the theorem

1124:

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

627:

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.

379:

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.

1099:

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

1594: 1257:

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

185:

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.

1246: 1651:

For graphs whose vertices are represented as pairs of points on two distinct surfaces, with edges drawn as non-crossing curves on one of the two surfaces, the chromatic number can be at least 9 and is at most 12, but more precise bounds are not known; this is

508:

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.

1100:

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.

467:

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:

343:

A student of mine asked 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

1151:

In the first map, which exceeds four colors, replacing the red regions with any of the four other colors would not work, and the example may initially appear to violate the theorem. However, the colors can be rearranged, as seen in the second

858: 1617: 1096:. 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. 535:, 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. 1380: 614:). 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. 1170:: 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. 1010:. 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. 373:

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.

1468: 1637: 339:. 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: 1545:). 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 ( 516:

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

1212:) 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 929:

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

623:(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 1173:

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.

89:, which can be shown using a significantly simpler argument. Although the weaker five color theorem was proven already in the 1800s, the four color theorem resisted until 1976 when it was proven by 1567: 960:

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

999:. 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 1083: 527:

to write an article addressing the rumors of flaws in their proof. They replied that the rumors were due to a "misinterpretation of results" and obliged with a detailed article. Their

245:

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:

1555: 189:

First, regions are adjacent if they share a boundary segment; two regions that share only isolated boundary points are not considered adjacent. (Otherwise, a map in a shape of a

952:

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

180: 702: 1006:

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

457: 3081: 1259: 141: 1204:

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

3443: 2880: 598:

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.

194:

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 has

1320: 979:

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

62:

means that two regions share a common boundary of non-zero length (i.e., not merely a corner where three or more regions meet). It was the first major

1092:). Then one "flows" the charge by systematically redistributing the charge from a vertex to its neighboring vertices according to a set of rules, the 1007: 441: 1220:) 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. 1408: 3396: 643:

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

543:

Since the proving of the theorem, a new approach has led to both a shorter proof and a more efficient algorithm for 4-coloring maps. In 1996,

3598: 3572: 2755: 2355: 2292: 327:, while trying to color the map of counties of England, noticed that only four different colors were needed. At the time, Guthrie's brother, 1628: 448:

Others took up his methods, including his computer-assisted approach. While other teams of mathematicians were racing to complete proofs,

58:, 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. 425: 3155: 1118:

The four color theorem has been notorious for attracting a large number of false proofs and disproofs in its long history. At first,

3668: 3653: 3520: 3378: 3276: 2590: 2442: 1897: 1688:(considered to be adjacent when two cuboids share a two-dimensional boundary area), an unbounded number of colors may be necessary. 259:

belong to the same country. If we wanted those regions to receive the same color, then five colors would be required, since the two

205:

subset of the plane) is not the same as that of a "country" on regular maps, since countries need not be contiguous (they may have

2688:

Borodin, O. V. (1984), "Solution of the Ringel problem on vertex-face coloring of planar graphs and coloring of 1-planar graphs",

1684:

can be taken to be any integer, as large as desired. Such examples were known to Fredrick Guthrie in 1880. Even for axis-parallel

2897: 2275:

Steinberg, Richard (1993), "The state of the three color problem", in Gimbel, John; Kennedy, John W.; Quintas, Louis V. (eds.),

2857: 1515: 1194: 3301: 3244: 2577:, Contemporary Mathematics, vol. 98, With the collaboration of J. Koch., Providence, RI: American Mathematical Society, 2247: 1159:

is focused on the one large region, they fail to notice that the remaining regions can in fact be colored with three colors.

544: 218: 3140: 488:

if the original map cannot be colored with four colors the smaller map cannot either and so the original map is not minimal.

476:

is a set of configurations such that every map that satisfies some necessary conditions for being a minimal non-4-colorable

3507:, London Mathematical Society Lecture Note Series, vol. 267, Cambridge: Cambridge University Press, pp. 201–222, 3625: 3456: 3017: 324: 1607:

into six mutually adjacent regions, requiring six colors. The vertices and edges of the subdivision form an embedding of

3560: 3500: 3467: 3431: 3313: 3309: 3256: 3252: 3197: 2778: 1984: 1879: 1579: 1488: 556: 552: 409:

Tait, in 1880, showed that the four color theorem is equivalent to the statement that a certain type of graph (called a

358: 1883: 1785: 3620: 3091: 504:

Appel and Haken's announcement was widely reported by the news media around the world, and the math department at the

198:, that is it entirely surrounds one or more other regions.) Note that the notion of "contiguous region" (technically: 2822:; Kalichanda, Bopanna; Mentis, Alexander S. (2009), "How false is Kempe's proof of the Four Color Theorem? Part II", 38: 3151: 1870: 1249:

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

1019: 523: 362:

in 1854, and De Morgan posed the question again in the same magazine in 1860. Another early published reference by

1181: 1788:: how many colors are needed to color the plane so that no two points at unit distance apart have the same color? 336: 2245:

Dailey, D. P. (1980), "Uniqueness of colorability and colorability of planar 4-regular graphs are NP-complete",

619: 2433:

Allaire, Frank (1978), "Another proof of the four colour theorem. I.", in D. McCarthy; H. C. Williams (eds.),

1775: 460:

announced, on June 21, 1976, that they had proved the theorem. They were assisted in some algorithmic work by

348:

are differently colored—four colors may be wanted but not more—the following is his case in which four colors

3658: 1105: 75: 67: 1668:

There is no obvious extension of the coloring result to three-dimensional solid regions. By using a set of

1657: 1495:, which has Euler characteristic 0 (hence the formula gives p = 7) but requires only 6 colors, as shown by 3663: 505: 316: 3615: 3046: 283: 1746: 1573:

An 8-coloured double torus (genus-two surface) – bubbles denote unique combination of two regions

1561:

A radially symmetric 7-colored torus – regions of the same colour wrap around along dotted lines

1166:

Perhaps one effect underlying this common misconception is the fact that the color restriction is not

3358: 3205: 3124: 3035: 2545: 1311: 1302:

is equivalent to that on the plane. For closed (orientable or non-orientable) surfaces with positive

652: 587: 580: 477: 410: 79: 983:

adjacent to a given configuration is fixed, and they are joined in a cycle. These vertices form the

150: 3346: 1982:(April 14, 1860), "The Philosophy of Discovery, Chapters Historical and Critical. By W. Whewell.", 1779: 1704: 1643: 1624: 1523: 1519: 1303: 1279: 1167: 287: 206: 195: 118: 1672:

flexible rods, one can arrange that every rod touches every other rod. The set would then require

461: 263:

regions together are adjacent to four other regions, each of which is adjacent to all the others.

3537: 3412: 3290: 3025: 2984: 2953: 2924: 2725: 2653: 2627: 2604: 1979: 1765: 1760: 1752: 1514:= 7, so no more than 7 colors are required to color any map on a torus. This upper bound of 7 is 1476: 1120: 946: 403: 388: 332: 226: 86: 71: 1294:

One can also consider the coloring problem on surfaces other than the plane. The problem on the

853:{\displaystyle 6v-2e=6\sum _{i=1}^{D}v_{i}-\sum _{i=1}^{D}iv_{i}=\sum _{i=1}^{D}(6-i)v_{i}=12.} 3594: 3568: 3516: 3384: 3374: 3305: 3272: 3248: 3233: 2773: 2751: 2586: 2438: 2351: 2288: 1893: 1889: 1608: 1283: 548: 512:

In the early 1980s, rumors spread of a flaw in the Appel–Haken proof. Ulrich Schmidt at

498: 328: 3503:(1999), "Recent Excluded Minor Theorems for Graphs", in Lamb, John D.; Preece, D. A. (eds.), 1286:, simply by expressing the colorability of an infinite graph with a set of logical formulae. 3549: 3508: 3404: 3366: 3321: 3264: 3223: 3213: 3132: 3087: 3058: 3004: 2976: 2945: 2868: 2844: 2831: 2808: 2741: 2717: 2669: 2637: 2578: 2553: 2512: 2475: 2343: 2335: 2280: 2279:, Annals of Discrete Mathematics, vol. 55, Amsterdam: North-Holland, pp. 211–248, 2256: 1998: 1917: 591: 576: 440:

developed methods of using computers to search for a proof. Notably he was the first to use

279: 210: 144: 102: 3582: 3530: 3452: 3424: 3335: 3286: 3072: 2893: 2804: 2765: 2697: 2681: 2649: 2600: 2526: 2489: 2452: 2365: 2302: 968:. If at least one of a set of configurations must occur somewhere in G, that set is called 97:. This came after many false proofs and mistaken counterexamples in the preceding decades. 3578: 3526: 3480: 3471: 3448: 3420: 3342: 3331: 3282: 3167: 3068: 2889: 2812: 2800: 2761: 2693: 2677: 2645: 2596: 2522: 2485: 2448: 2435:

Proceedings, 7th Manitoba Conference on Numerical Mathematics and Computing, Congr. Numer.

2361: 2298: 1905: 1875: 1600: 1496: 1233: 1142: 1133: 617:

Kempe's argument goes as follows. First, if planar regions separated by the graph are not

560: 437: 396: 266: 234: 199: 106: 1604: 1530: 3362: 3209: 3128: 3039: 2549: 30: 3193: 3181: 2615: 2568: 2557: 2537: 2500: 2463: 1770: 1696: 1653: 1538: 1484: 1386: 1254: 1245: 595: 564: 453: 428:, a far-reaching generalization of the four-color problem that still remains unsolved. 295: 248: 126: 94: 3228: 3063: 2872: 2437:, vol. 20, Winnipeg, Man.: Utilitas Mathematica Publishing, Inc., pp. 3–72, 2284: 3647: 2908: 2848: 2819: 2788: 2705: 2564: 2533: 2496: 2459: 2342:, Problem Books in Mathematics, Springer International Publishing, pp. 115–133, 2327: 2261: 1732: 1720: 1480: 1275: 906:

and extend the four-coloring to it by choosing a color different from its neighbors.

480:(such as having minimum degree 5) must have at least one configuration from this set. 449: 421: 392: 363: 242: 90: 3294: 1922: 1237:

By joining the single arrows together and the double arrows together, one obtains a

3638: 3403:, vol. 87, no. 9, Mathematical Association of America, pp. 697–702, 3105: 2964: 2791:; Springer, W. M. (2003), "How false is Kempe's proof of the four color theorem?", 2657: 2608: 2331: 1716: 1700: 1586: 1492: 624: 414: 384: 291: 275: 121: 17: 3109: 3108:; Melendez, J.; Berenguer, R.; Sendra, J. R.; Hernandez, A.; Del Pino, J. (2002), 2740:, Translated from the 1994 German original by Julie Peschke., New York: Springer, 2572: 311: 3370: 2347: 1873:

originated the four-color conjecture, but this notion seems to be erroneous. See

1375:{\displaystyle p=\left\lfloor {\frac {7+{\sqrt {49-24\chi }}}{2}}\right\rfloor ,} 1197:

to decide whether an arbitrary planar map can be colored with just three colors.

42:

A four-colored map of the states of the United States (ignoring lakes and oceans)

3435: 1724: 1201: 1190: 995:-ring configuration, and the configuration together with its ring is called the 930: 913:

A graph containing a Kempe chain consisting of alternating blue and red vertices

528: 513: 323:

As far as is known, the conjecture was first proposed on October 23, 1852, when

82:. The proof has gained wide acceptance since then, although some doubts remain. 47: 3485:"Einige Bemerkungen über das Problem des Kartenfärbens auf einseitigen Flächen" 2836: 878:

such graph, where removing any vertex makes it four-colorable. Call this graph

402:

In 1890, in addition to exposing the flaw in Kempe's proof, Heawood proved the

270:

A map with four regions, and the corresponding planar graph with four vertices.

3553: 2746: 1742: 1393: 871:≥ 6, this demonstrates that there is at least one vertex of degree 5 or less. 494: 222: 3512: 3487:[Some remarks on the problem of map coloring on one-sided surfaces], 3136: 2995:

Magnant, C.; Martin, D. M. (2011), "Coloring rectangular blocks in 3-space",

2517: 2503:; Koch, John (1977), "Every Planar Map is Four Colorable. II. Reducibility", 2480: 1253:

The four color theorem applies not only to finite planar graphs, but also to

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

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

190: 3388: 3326: 3237: 2673: 1241:

with seven mutually touching regions; therefore seven colors are necessary.

3268: 3218: 2738:

The Four Color Theorem: History, Topological Foundations and Idea of Proof

2005:, in Mathematical Recreations and Essays, Macmillan, New York, pp 222–232. 1646:

that the number of colours needed is unbounded in three or more dimensions

497:, which had to be checked by hand with the assistance of Haken's daughter 406:

and generalized the four color conjecture to surfaces of arbitrary genus.

1299: 1205: 391:

in 1880. It was not until 1890 that Kempe's proof was shown incorrect by

202: 3567:, Princeton Science Library, Princeton, NJ: Princeton University Press, 3261:

Proceedings of the 28th ACM Symposium on Theory of Computing (STOC 1996)

909: 3416: 2988: 2957: 2729: 2641: 2582: 1185:

Proof without words that a map of US states needs at least four colors.

290:

for every pair of regions that share a boundary segment. This graph is

278:. The set of regions of a map can be represented more abstractly as an 63: 3009: 2632: 1728: 1685: 1680:+1 including the empty space that also touches every rod. The number 1396:

surface the formula can be given in terms of the genus of a surface,

1295: 1213: 238: 230: 214: 3634: 3408: 2980: 2949: 2721: 606:

The following discussion is a summary based on the introduction to

356:"F.G.", perhaps one of the two Guthries, published the question in 3030: 1503: 1238: 1180: 908: 310: 265: 37: 29: 2664:

Bernhart, Frank R. (1977), "A digest of the four color theorem",

925:

and four-color the remaining vertices. If all four neighbors of

3589:

Wilson, Robin; Watkins, John J.; Parks, David J. (2023-01-17),

3484: 1262:

stating that, if every finite subgraph of an infinite graph is

921:

can have no vertex of degree 4. As before we remove the vertex

2466:(1977), "Every Planar Map is Four Colorable. I. Discharging", 1627:

model with each of 7 faces adjacent to every other – in

1483:

in 1890 and, after contributions by several people, proved by

1189:

While every planar map can be colored with four colors, it is

352:

wanted. Query cannot a necessity for five or more be invented…

2192: 247: 2967:(1879), "On the Geographical Problem of the Four Colours", 2220: 1908:(1897), "Note on the history of the map-coloring problem", 3397:"The philosophical implications of the four-color problem" 2540:(October 1977), "Solution of the Four Color Map Problem", 1541:(graphs drawn with at most one simple crossing per edge) ( 387:

in 1879, which was widely acclaimed; another was given by

3349:(1986), "The Four Color Problem: Assaults and Conquest", 2911:(1943), "Über eine Klassifikation der Streckenkomplexe", 2118: 2116: 3200:(1968), "Solution of the Heawood Map-Coloring Problem", 2340:

Graph Theory: Favorite Conjectures and Open Problems, II

2172: 2170: 2133: 2131: 945:

use Kempe chains in the degree 5 situation to prove the

874:

If there is a graph requiring 5 colors, then there is a

521:). In 1986, Appel and Haken were asked by the editor of 1274:. This can also be seen as an immediate consequence of 445:

the necessary supercomputer time to continue his work.

2936:

Hudson, Hud (May 2003), "Four Colors Do Not Suffice",

117:

In graph-theoretic terms, the theorem states that for

1411: 1323: 1022: 886:

cannot have a vertex of degree 3 or less, because if

705: 583:

conjecture. This proof remains unpublished, however.

153: 129: 3489:

Jahresbericht der Deutschen Mathematiker-Vereinigung

3259:(1996), "Efficiently four-coloring planar graphs", 3022:

A note on the history of the four-colour conjecture

2850:

A computer-checked proof of the four colour theorem

2618:(1997), "Lie algebras and the four color theorem", 1088:

Each vertex is assigned an initial charge of 6-deg(

679:of a vertex is the number of edges abutting it. If 399:—each false proof stood unchallenged for 11 years. 395:, and in 1891, Tait's proof was shown incorrect by 74:was not accepted by all mathematicians because the 1491:in 1968. The only exception to the formula is the 1462: 1374: 1163:counterexample will appear as though it is valid. 1077: 852: 174: 135: 3635:List of generalizations of the four color theorem 436:During the 1960s and 1970s, German mathematician 3593:, Princeton Oxford: Princeton University Press, 1974: 1972: 1723:. According to an article by the math historian 3110:"Book Review: The Colossal Book of Mathematics" 2544:, vol. 237, no. 4, pp. 108–121, 1719:, the theorem is not of particular interest to 1707:which is equivalent to the four color theorem. 370:) in turn credits the conjecture to De Morgan. 3447:, vol. 45, no. 7, pp. 848–859, 3204:, vol. 60, no. 2, pp. 438–445, 902:, four-color the smaller graph, then add back 3540:(1880), "Remarks on the colourings of maps", 2710:Proceedings of the Royal Geographical Society 2668:, vol. 1, no. 3, pp. 207–225, 2393: 2389: 1937:Mechanizing Proof: Computing, Risk, and Trust 1271: 1078:{\displaystyle \sum _{i=1}^{D}(6-i)v_{i}=12.} 594:formalized a proof of the theorem inside the 8: 3444:Notices of the American Mathematical Society 3117:Notices of the American Mathematical Society 2881:Notices of the American Mathematical Society 3357:(4366), New York: Dover Publications: 424, 3320:, vol. 70, no. 1, pp. 2–44, 987:of the configuration; a configuration with 575:is the number of vertices), improving on a 2122: 2103: 1869:There is some mathematical folk-lore that 1506:has Euler characteristic χ = 0 (and genus 1310:of colors needed depends on the surface's 611: 518: 3325: 3227: 3217: 3062: 3029: 3008: 2835: 2745: 2631: 2516: 2479: 2404: 2260: 1921: 1431: 1422: 1410: 1343: 1334: 1322: 1266:-colorable, then the whole graph is also 1063: 1038: 1027: 1021: 838: 813: 802: 789: 776: 765: 752: 742: 731: 704: 152: 128: 85:The theorem is a stronger version of the 2929:Quarterly Journal of Mathematics, Oxford 2736:Fritsch, Rudolf; Fritsch, Gerda (1998), 2232: 2050: 1805: 1385:where the outermost brackets denote the 1244: 1232: 274:A simpler statement of the theorem uses 2026: 1797: 1551: 1546: 1542: 1125:amateurs, were never published at all. 937:can now be added back and colored red. 80:infeasible for a human to check by hand 2997:Discussiones Mathematicae Graph Theory 2913:Vierteljschr. Naturforsch. Ges. Zürich 2416: 2377: 2314: 2216: 2204: 2188: 2176: 2161: 2149: 2137: 2107: 2099: 2087: 2062: 2014: 1948: 1857: 1853: 1841: 1829: 1692:Relation to other areas of mathematics 1534: 367: 3436:"An Update on the Four-Color Theorem" 2873:"Formal Proof—The Four-Color Theorem" 2708:(1879), "On the colourings of maps", 2330:(2018), "To the Moon and beyond", in 1964: 1960: 1817: 696:is the maximum degree of any vertex, 255:In this map, the two regions labeled 7: 3160:Mathematics-in-Industry Case Studies 3049:(1967), "Infinite graphs—a survey", 2716:(4), Blackwell Publishing: 259–261, 2038: 1717:coloring political maps of countries 688:is the number of vertices of degree 3316:(1997), "The Four-Colour Theorem", 956:, which are connected subgraphs of 413:in modern terminology) must be non- 335:(the former advisor of Francis) at 3188:, New York–Berlin: Springer-Verlag 2574:Every Planar Map is Four-Colorable 2558:10.1038/scientificamerican1077-108 2074:Gary Chartrand and Linda Lesniak, 608:Every Planar Map is Four Colorable 533:Every Planar Map is Four-Colorable 113:Precise formulation of the theorem 25: 2938:The American Mathematical Monthly 2338:; Hedetniemi, Stephen T. (eds.), 917:Kempe also showed correctly that 2931:, vol. 24, pp. 332–338 1745: 1636: 1616: 1593: 1578: 1566: 1554: 1141: 1132: 940:This leaves only the case where 383:One proposed proof was given by 3462:from the original on 2000-09-29 3146:from the original on 2003-04-09 3051:Journal of Combinatorial Theory 2969:American Journal of Mathematics 2903:from the original on 2011-08-05 2863:from the original on 2017-09-08 2505:Illinois Journal of Mathematics 2468:Illinois Journal of Mathematics 1980:De Morgan (anonymous), Augustus 1923:10.1090/S0002-9904-1897-00421-9 667:= 2, can be used to show that 6 539:Simplification and verification 3505:Surveys in combinatorics, 1999 3395:Swart, Edward Reinier (1980), 2927:(1890), "Map-Colour Theorem", 1782:planar graphs are 3-colorable. 1056: 1044: 831: 819: 175:{\displaystyle \chi (G)\leq 4} 163: 157: 1: 3401:American Mathematical Monthly 3064:10.1016/s0021-9800(67)80077-2 2285:10.1016/S0167-5060(08)70391-1 1631:, move the mouse to rotate it 34:Example of a four-colored map 3371:10.1126/science.202.4366.424 3080:O'Connor; Robertson (1996), 2348:10.1007/978-3-319-97686-0_11 2262:10.1016/0012-365X(80)90236-8 1715:Despite the motivation from 1699:gave a statement concerning 863:But since 12 > 0 and 6 − 3621:Encyclopedia of Mathematics 3154:; Allwright, David (2008), 3047:Nash-Williams, C. St. J. A. 2394:Magnant & Martin (2011) 1888:, Oxford University Press, 1314:χ according to the formula 3685: 3202:Proc. Natl. Acad. Sci. USA 2837:10.2140/involve.2009.2.249 2690:Metody Diskretnogo Analiza 1735:) be colored identically. 1711:Use outside of mathematics 1013:Recall the formula above: 991:vertices in its ring is a 563:algorithm (requiring only 524:Mathematical Intelligencer 3554:10.1017/S0370164600044643 2747:10.1007/978-1-4612-1720-6 2390:Reed & Allwright 2008 337:University College London 3669:Theorems in graph theory 3654:Computer-assisted proofs 3513:10.1017/CBO9780511721335 3318:J. Combin. Theory Ser. B 3137:10.1109/TED.2002.1003756 2277:Quo Vadis, Graph Theory? 2123:Appel & Haken (1989) 2104:Appel & Haken (1989) 107:theorem-proving software 105:using a general-purpose 27:Statement in mathematics 3591:Graph Theory in America 3542:Proc. R. Soc. Edinburgh 3083:The Four Colour Theorem 2772:F. G. (June 10, 1854), 2666:Journal of Graph Theory 2193:Robertson et al. (1996) 2078:(CRC Press, 2005) p.221 1885:Graph Theory, 1736–1936 1786:Hadwiger–Nelson problem 1260:De Bruijn–Erdős theorem 966:reducible configuration 485:reducible configuration 315:Letter of De Morgan to 286:for each region and an 76:computer-assisted proof 68:proved using a computer 3473:The Four Color Theorem 3327:10.1006/jctb.1997.1750 2674:10.1002/jgt.3190010305 2518:10.1215/ijm/1256049012 2481:10.1215/ijm/1256049011 2003:The Four Color Theorem 1939:(MIT Press, 2004) p103 1910:Bull. Amer. Math. Soc. 1526:require seven colors. 1464: 1392:Alternatively, for an 1376: 1250: 1242: 1186: 1079: 1043: 914: 854: 818: 781: 747: 612:Appel & Haken 1989 602:Summary of proof ideas 519:Appel & Haken 1989 506:University of Illinois 458:University of Illinois 381: 354: 320: 317:William Rowan Hamilton 271: 252: 176: 137: 56:four color map theorem 43: 35: 3616:"Four-colour problem" 3269:10.1145/237814.238005 3219:10.1073/pnas.60.2.438 3166:: 1–8, archived from 3156:"Painting the office" 2102:, pp. 105–107); 2076:Graphs & Digraphs 1533:requires six colors ( 1465: 1377: 1306:, the maximum number 1248: 1236: 1184: 1094:discharging procedure 1080: 1023: 1008:method of discharging 912: 894:) ≤ 3, we can remove 855: 798: 761: 727: 651:. This together with 376: 341: 314: 269: 251: 177: 138: 41: 33: 3263:, pp. 571–575, 2248:Discrete Mathematics 1731:and the rest of the 1705:Vassiliev invariants 1409: 1321: 1312:Euler characteristic 1272:Nash-Williams (1967) 1020: 997:ringed configuration 703: 307:Early proof attempts 235:overseas territories 151: 127: 3565:Four Colors Suffice 3363:1978Sci...202..424S 3210:1968PNAS...60..438R 3129:2002ITED...49.1084A 3040:2012arXiv1201.2852M 2550:1977SciAm.237d.108A 2542:Scientific American 2207:, pp. 852–853. 2110:, pp. 852–853) 2090:, pp. 145–146. 2065:, pp. 139–142. 1878:; Lloyd, E. Keith; 1644:Proof without words 1625:Szilassi polyhedron 1524:Szilassi polyhedron 1280:compactness theorem 426:Hadwiger conjecture 331:, was a student of 229:as part of Russia, 18:Four colour theorem 3306:Sanders, Daniel P. 3249:Sanders, Daniel P. 2692:(41): 12–26, 108, 2642:10.1007/BF01196130 2221:Pegg et al. (2002) 1935:Donald MacKenzie, 1776:Grötzsch's theorem 1766:Five color theorem 1761:Apollonian network 1753:Mathematics portal 1658:Earth–Moon problem 1520:toroidal polyhedra 1479:, was proposed by 1477:Heawood conjecture 1475:This formula, the 1460: 1372: 1251: 1243: 1187: 1121:The New York Times 1075: 947:five color theorem 915: 850: 625:triangulated graph 404:five color theorem 389:Peter Guthrie Tait 333:Augustus De Morgan 321: 272: 253: 172: 133: 87:five color theorem 70:. Initially, this 52:four color theorem 44: 36: 3600:978-0-691-19402-8 3574:978-0-691-15822-8 3186:Map Color Theorem 3018:McKay, Brendan D. 3010:10.7151/dmgt.1535 2888:(11): 1382–1393, 2869:Gonthier, Georges 2845:Gonthier, Georges 2757:978-0-387-98497-1 2357:978-3-319-97684-6 2336:Haynes, Teresa W. 2294:978-0-444-89441-0 1603:subdivision of a 1502:For example, the 1451: 1445: 1363: 1357: 1284:first-order logic 549:Daniel P. Sanders 499:Dorothea Blostein 432:Proof by computer 364:Arthur Cayley 136:{\displaystyle G} 16:(Redirected from 3676: 3629: 3603: 3585: 3556: 3533: 3496: 3481:Tietze, Heinrich 3476: 3463: 3461: 3440: 3427: 3391: 3338: 3329: 3297: 3240: 3231: 3221: 3198:Youngs, J. W. T. 3189: 3177: 3176: 3175: 3147: 3145: 3123:(9): 1084–1086, 3114: 3101: 3100: 3099: 3090:, archived from 3088:MacTutor archive 3075: 3066: 3042: 3033: 3013: 3012: 2991: 2960: 2932: 2920: 2904: 2902: 2877: 2864: 2862: 2855: 2840: 2839: 2815: 2783: 2768: 2749: 2732: 2700: 2684: 2660: 2635: 2611: 2583:10.1090/conm/098 2560: 2529: 2520: 2492: 2483: 2455: 2420: 2414: 2408: 2405:Bar-Natan (1997) 2402: 2396: 2387: 2381: 2375: 2369: 2368: 2324: 2318: 2312: 2306: 2305: 2272: 2266: 2265: 2264: 2242: 2236: 2230: 2224: 2214: 2208: 2202: 2196: 2186: 2180: 2174: 2165: 2159: 2153: 2147: 2141: 2135: 2126: 2120: 2111: 2097: 2091: 2085: 2079: 2072: 2066: 2060: 2054: 2048: 2042: 2036: 2030: 2024: 2018: 2012: 2006: 1999:W. W. Rouse Ball 1996: 1990: 1989: 1976: 1967: 1958: 1952: 1946: 1940: 1933: 1927: 1926: 1925: 1906:Maddison, Isabel 1902: 1880:Wilson, Robin J. 1867: 1861: 1856:, p. 849); 1851: 1845: 1839: 1833: 1827: 1821: 1815: 1809: 1802: 1755: 1750: 1749: 1640: 1620: 1597: 1582: 1570: 1558: 1469: 1467: 1466: 1461: 1456: 1452: 1447: 1446: 1432: 1423: 1381: 1379: 1378: 1373: 1368: 1364: 1359: 1358: 1344: 1335: 1145: 1136: 1084: 1082: 1081: 1076: 1068: 1067: 1042: 1037: 859: 857: 856: 851: 843: 842: 817: 812: 794: 793: 780: 775: 757: 756: 746: 741: 592:Georges Gonthier 280:undirected graph 211:Cabinda Province 181: 179: 178: 173: 145:chromatic number 142: 140: 139: 134: 103:Georges Gonthier 101:was verified by 21: 3684: 3683: 3679: 3678: 3677: 3675: 3674: 3673: 3644: 3643: 3614: 3611: 3606: 3601: 3588: 3575: 3559: 3536: 3523: 3499: 3479: 3466: 3459: 3438: 3430: 3409:10.2307/2321855 3394: 3381: 3341: 3302:Robertson, Neil 3300: 3279: 3245:Robertson, Neil 3243: 3192: 3180: 3173: 3171: 3150: 3143: 3112: 3104: 3097: 3095: 3079: 3045: 3016: 2994: 2981:10.2307/2369235 2963: 2950:10.2307/3647828 2935: 2923: 2907: 2900: 2875: 2867: 2860: 2856:, unpublished, 2853: 2843: 2818: 2787: 2771: 2758: 2735: 2722:10.2307/1799998 2704: 2687: 2663: 2616:Bar-Natan, Dror 2614: 2593: 2569:Haken, Wolfgang 2563: 2538:Haken, Wolfgang 2532: 2501:Haken, Wolfgang 2495: 2464:Haken, Wolfgang 2458: 2445: 2432: 2428: 2423: 2415: 2411: 2403: 2399: 2388: 2384: 2376: 2372: 2358: 2326: 2325: 2321: 2313: 2309: 2295: 2274: 2273: 2269: 2244: 2243: 2239: 2233:Gonthier (2008) 2231: 2227: 2215: 2211: 2203: 2199: 2187: 2183: 2175: 2168: 2160: 2156: 2148: 2144: 2136: 2129: 2121: 2114: 2098: 2094: 2086: 2082: 2073: 2069: 2061: 2057: 2051:Hadwiger (1943) 2049: 2045: 2037: 2033: 2025: 2021: 2013: 2009: 1997: 1993: 1978: 1977: 1970: 1959: 1955: 1947: 1943: 1934: 1930: 1904: 1900: 1874: 1868: 1864: 1852: 1848: 1840: 1836: 1828: 1824: 1816: 1812: 1806:Gonthier (2008) 1803: 1799: 1795: 1751: 1744: 1741: 1713: 1694: 1666: 1647: 1641: 1632: 1621: 1612: 1611:onto the strip. 1598: 1589: 1583: 1574: 1571: 1562: 1559: 1539:1-planar graphs 1497:Philip Franklin 1489:J. W. T. Youngs 1424: 1418: 1407: 1406: 1336: 1330: 1319: 1318: 1292: 1290:Higher surfaces 1255:infinite graphs 1231: 1229:Infinite graphs 1226: 1224:Generalizations 1179: 1156: 1155: 1154: 1153: 1148: 1147: 1146: 1138: 1137: 1116: 1114:False disproofs 1059: 1018: 1017: 834: 785: 748: 701: 700: 687: 675:= 12. Now, the 653:Euler's formula 604: 588:Benjamin Werner 541: 474:unavoidable set 438:Heinrich Heesch 434: 424:formulated the 397:Julius Petersen 325:Francis Guthrie 309: 304: 241:as part of the 149: 148: 125: 124: 115: 28: 23: 22: 15: 12: 11: 5: 3682: 3680: 3672: 3671: 3666: 3661: 3659:Graph coloring 3656: 3646: 3645: 3642: 3641: 3631: 3630: 3610: 3609:External links 3607: 3605: 3604: 3599: 3586: 3573: 3557: 3534: 3521: 3497: 3477: 3464: 3428: 3392: 3379: 3339: 3298: 3277: 3241: 3190: 3178: 3148: 3102: 3077: 3057:(3): 286–301, 3043: 3014: 3003:(1): 161–170, 2992: 2975:(3): 193–220, 2961: 2944:(5): 417–423, 2933: 2925:Heawood, P. J. 2921: 2909:Hadwiger, Hugo 2905: 2865: 2841: 2830:(3): 249–265, 2820:Gethner, Ellen 2816: 2785: 2774:"Tinting Maps" 2769: 2756: 2733: 2706:Cayley, Arthur 2702: 2685: 2661: 2612: 2591: 2565:Appel, Kenneth 2561: 2534:Appel, Kenneth 2530: 2511:(3): 491–567, 2497:Appel, Kenneth 2493: 2474:(3): 429–490, 2460:Appel, Kenneth 2456: 2443: 2429: 2427: 2424: 2422: 2421: 2409: 2397: 2382: 2370: 2356: 2328:Gethner, Ellen 2319: 2307: 2293: 2267: 2255:(3): 289–293, 2237: 2225: 2209: 2197: 2181: 2179:, p. 165. 2166: 2164:, p. 157. 2154: 2152:, p. 150. 2142: 2140:, p. 153. 2127: 2112: 2092: 2080: 2067: 2055: 2043: 2031: 2027:Heawood (1890) 2019: 2017:, p. 848. 2007: 1991: 1968: 1953: 1941: 1928: 1898: 1862: 1846: 1834: 1822: 1810: 1796: 1794: 1791: 1790: 1789: 1783: 1773: 1771:Graph coloring 1768: 1763: 1757: 1756: 1740: 1737: 1712: 1709: 1697:Dror Bar-Natan 1693: 1690: 1665: 1662: 1654:Gerhard Ringel 1649: 1648: 1642: 1635: 1633: 1622: 1615: 1613: 1609:Tietze's graph 1599: 1592: 1590: 1584: 1577: 1575: 1572: 1565: 1563: 1560: 1553: 1510:= 1) and thus 1485:Gerhard Ringel 1473: 1472: 1471: 1470: 1459: 1455: 1450: 1444: 1441: 1438: 1435: 1430: 1427: 1421: 1417: 1414: 1387:floor function 1383: 1382: 1371: 1367: 1362: 1356: 1353: 1350: 1347: 1342: 1339: 1333: 1329: 1326: 1291: 1288: 1230: 1227: 1225: 1222: 1178: 1177:Three-coloring 1175: 1150: 1149: 1140: 1139: 1131: 1130: 1129: 1128: 1127: 1115: 1112: 1086: 1085: 1074: 1071: 1066: 1062: 1058: 1055: 1052: 1049: 1046: 1041: 1036: 1033: 1030: 1026: 1001:initially good 954:configurations 861: 860: 849: 846: 841: 837: 833: 830: 827: 824: 821: 816: 811: 808: 805: 801: 797: 792: 788: 784: 779: 774: 771: 768: 764: 760: 755: 751: 745: 740: 737: 734: 730: 726: 723: 720: 717: 714: 711: 708: 683: 603: 600: 571:) time, where 561:quadratic-time 545:Neil Robertson 540: 537: 490: 489: 481: 454:Wolfgang Haken 433: 430: 319:, 23 Oct. 1852 308: 305: 303: 300: 296:four-colorable 171: 168: 165: 162: 159: 156: 132: 114: 111: 95:Wolfgang Haken 26: 24: 14: 13: 10: 9: 6: 4: 3: 2: 3681: 3670: 3667: 3665: 3664:Planar graphs 3662: 3660: 3657: 3655: 3652: 3651: 3649: 3640: 3636: 3633: 3632: 3627: 3623: 3622: 3617: 3613: 3612: 3608: 3602: 3596: 3592: 3587: 3584: 3580: 3576: 3570: 3566: 3562: 3561:Wilson, Robin 3558: 3555: 3551: 3547: 3543: 3539: 3535: 3532: 3528: 3524: 3522:0-521-65376-2 3518: 3514: 3510: 3506: 3502: 3501:Thomas, Robin 3498: 3494: 3490: 3486: 3482: 3478: 3475: 3474: 3469: 3468:Thomas, Robin 3465: 3458: 3454: 3450: 3446: 3445: 3437: 3433: 3432:Thomas, Robin 3429: 3426: 3422: 3418: 3414: 3410: 3406: 3402: 3398: 3393: 3390: 3386: 3382: 3380:0-486-65092-8 3376: 3372: 3368: 3364: 3360: 3356: 3352: 3348: 3344: 3343:Saaty, Thomas 3340: 3337: 3333: 3328: 3323: 3319: 3315: 3314:Thomas, Robin 3311: 3310:Seymour, Paul 3307: 3303: 3299: 3296: 3292: 3288: 3284: 3280: 3278:0-89791-785-5 3274: 3270: 3266: 3262: 3258: 3257:Thomas, Robin 3254: 3253:Seymour, Paul 3250: 3246: 3242: 3239: 3235: 3230: 3225: 3220: 3215: 3211: 3207: 3203: 3199: 3195: 3191: 3187: 3183: 3179: 3170:on 2013-02-03 3169: 3165: 3161: 3157: 3153: 3149: 3142: 3138: 3134: 3130: 3126: 3122: 3118: 3111: 3107: 3103: 3094:on 2013-01-16 3093: 3089: 3085: 3084: 3078: 3074: 3070: 3065: 3060: 3056: 3052: 3048: 3044: 3041: 3037: 3032: 3027: 3023: 3019: 3015: 3011: 3006: 3002: 2998: 2993: 2990: 2986: 2982: 2978: 2974: 2970: 2966: 2962: 2959: 2955: 2951: 2947: 2943: 2939: 2934: 2930: 2926: 2922: 2918: 2914: 2910: 2906: 2899: 2895: 2891: 2887: 2883: 2882: 2874: 2870: 2866: 2859: 2852: 2851: 2846: 2842: 2838: 2833: 2829: 2825: 2821: 2817: 2814: 2810: 2806: 2802: 2798: 2794: 2790: 2786: 2781: 2780: 2779:The Athenaeum 2775: 2770: 2767: 2763: 2759: 2753: 2748: 2743: 2739: 2734: 2731: 2727: 2723: 2719: 2715: 2711: 2707: 2703: 2699: 2695: 2691: 2686: 2683: 2679: 2675: 2671: 2667: 2662: 2659: 2655: 2651: 2647: 2643: 2639: 2634: 2633:q-alg/9606016 2629: 2625: 2621: 2620:Combinatorica 2617: 2613: 2610: 2606: 2602: 2598: 2594: 2592:0-8218-5103-9 2588: 2584: 2580: 2576: 2575: 2570: 2566: 2562: 2559: 2555: 2551: 2547: 2543: 2539: 2535: 2531: 2528: 2524: 2519: 2514: 2510: 2506: 2502: 2498: 2494: 2491: 2487: 2482: 2477: 2473: 2469: 2465: 2461: 2457: 2454: 2450: 2446: 2444:0-919628-20-6 2440: 2436: 2431: 2430: 2425: 2418: 2417:Wilson (2014) 2413: 2410: 2406: 2401: 2398: 2395: 2391: 2386: 2383: 2380:, p. 15. 2379: 2378:Wilson (2014) 2374: 2371: 2367: 2363: 2359: 2353: 2349: 2345: 2341: 2337: 2333: 2332:Gera, Ralucca 2329: 2323: 2320: 2316: 2315:Ringel (1974) 2311: 2308: 2304: 2300: 2296: 2290: 2286: 2282: 2278: 2271: 2268: 2263: 2258: 2254: 2250: 2249: 2241: 2238: 2234: 2229: 2226: 2222: 2218: 2217:Thomas (1999) 2213: 2210: 2206: 2205:Thomas (1998) 2201: 2198: 2194: 2190: 2189:Thomas (1995) 2185: 2182: 2178: 2177:Wilson (2014) 2173: 2171: 2167: 2163: 2162:Wilson (2014) 2158: 2155: 2151: 2150:Wilson (2014) 2146: 2143: 2139: 2138:Wilson (2014) 2134: 2132: 2128: 2124: 2119: 2117: 2113: 2109: 2105: 2101: 2096: 2093: 2089: 2088:Wilson (2014) 2084: 2081: 2077: 2071: 2068: 2064: 2063:Wilson (2014) 2059: 2056: 2052: 2047: 2044: 2040: 2035: 2032: 2028: 2023: 2020: 2016: 2015:Thomas (1998) 2011: 2008: 2004: 2000: 1995: 1992: 1987: 1986: 1985:The Athenaeum 1981: 1975: 1973: 1969: 1966: 1962: 1957: 1954: 1951:, p. 12. 1950: 1949:Wilson (2014) 1945: 1942: 1938: 1932: 1929: 1924: 1919: 1915: 1911: 1907: 1901: 1899:0-19-853916-9 1895: 1891: 1887: 1886: 1881: 1877: 1876:Biggs, Norman 1872: 1866: 1863: 1859: 1858:Wilson (2014) 1855: 1850: 1847: 1843: 1842:Hudson (2003) 1838: 1835: 1831: 1830:Wilson (2014) 1826: 1823: 1819: 1814: 1811: 1807: 1801: 1798: 1792: 1787: 1784: 1781: 1780:triangle-free 1777: 1774: 1772: 1769: 1767: 1764: 1762: 1759: 1758: 1754: 1748: 1743: 1738: 1736: 1734: 1733:United States 1730: 1726: 1722: 1721:cartographers 1718: 1710: 1708: 1706: 1702: 1698: 1691: 1689: 1687: 1683: 1679: 1675: 1671: 1664:Solid regions 1663: 1661: 1659: 1655: 1645: 1639: 1634: 1630: 1629:the SVG image 1626: 1619: 1614: 1610: 1606: 1602: 1596: 1591: 1588: 1581: 1576: 1569: 1564: 1557: 1552: 1550: 1548: 1544: 1540: 1536: 1532: 1527: 1525: 1521: 1517: 1513: 1509: 1505: 1500: 1498: 1494: 1490: 1486: 1482: 1481:P. J. Heawood 1478: 1457: 1453: 1448: 1442: 1439: 1436: 1433: 1428: 1425: 1419: 1415: 1412: 1405: 1404: 1403: 1402: 1401: 1399: 1395: 1390: 1388: 1369: 1365: 1360: 1354: 1351: 1348: 1345: 1340: 1337: 1331: 1327: 1324: 1317: 1316: 1315: 1313: 1309: 1305: 1301: 1297: 1289: 1287: 1285: 1281: 1277: 1273: 1269: 1265: 1261: 1256: 1247: 1240: 1235: 1228: 1223: 1221: 1219: 1215: 1211: 1207: 1203: 1198: 1196: 1192: 1183: 1176: 1174: 1171: 1169: 1164: 1160: 1144: 1135: 1126: 1123: 1122: 1113: 1111: 1109: 1107: 1101: 1097: 1095: 1091: 1072: 1069: 1064: 1060: 1053: 1050: 1047: 1039: 1034: 1031: 1028: 1024: 1016: 1015: 1014: 1011: 1009: 1004: 1002: 998: 994: 990: 986: 982: 978: 973: 971: 967: 963: 959: 955: 950: 948: 943: 938: 936: 932: 928: 924: 920: 911: 907: 905: 901: 897: 893: 889: 885: 881: 877: 872: 870: 866: 847: 844: 839: 835: 828: 825: 822: 814: 809: 806: 803: 799: 795: 790: 786: 782: 777: 772: 769: 766: 762: 758: 753: 749: 743: 738: 735: 732: 728: 724: 721: 718: 715: 712: 709: 706: 699: 698: 697: 695: 691: 686: 682: 678: 674: 670: 666: 662: 658: 654: 650: 646: 642: 638: 634: 629: 626: 622: 621: 615: 613: 609: 601: 599: 597: 593: 589: 584: 582: 578: 574: 570: 566: 562: 558: 554: 550: 546: 538: 536: 534: 530: 526: 525: 520: 515: 510: 507: 502: 500: 496: 486: 482: 479: 478:triangulation 475: 471: 470: 469: 465: 463: 459: 455: 451: 450:Kenneth Appel 446: 443: 439: 431: 429: 427: 423: 422:Hugo Hadwiger 418: 416: 412: 407: 405: 400: 398: 394: 393:Percy Heawood 390: 386: 380: 375: 371: 369: 365: 361: 360: 359:The Athenaeum 353: 351: 347: 340: 338: 334: 330: 326: 318: 313: 306: 301: 299: 297: 293: 289: 285: 281: 277: 268: 264: 262: 258: 250: 246: 244: 243:United States 240: 236: 232: 228: 224: 220: 216: 212: 208: 204: 201: 197: 192: 187: 183: 169: 166: 160: 154: 146: 130: 123: 120: 112: 110: 108: 104: 98: 96: 92: 91:Kenneth Appel 88: 83: 81: 77: 73: 69: 65: 61: 57: 53: 49: 40: 32: 19: 3639:MathOverflow 3619: 3590: 3564: 3545: 3541: 3504: 3492: 3488: 3472: 3442: 3400: 3354: 3350: 3347:Kainen, Paul 3317: 3260: 3201: 3185: 3172:, retrieved 3168:the original 3163: 3159: 3120: 3116: 3106:Pegg, Ed Jr. 3096:, retrieved 3092:the original 3082: 3054: 3050: 3021: 3000: 2996: 2972: 2968: 2965:Kempe, A. B. 2941: 2937: 2928: 2916: 2912: 2885: 2879: 2849: 2827: 2823: 2796: 2793:Congr. Numer 2792: 2777: 2737: 2713: 2709: 2689: 2665: 2626:(1): 43–52, 2623: 2619: 2573: 2541: 2508: 2504: 2471: 2467: 2434: 2412: 2400: 2385: 2373: 2339: 2322: 2310: 2276: 2270: 2252: 2246: 2240: 2228: 2212: 2200: 2184: 2157: 2145: 2108:Thomas (1998 2100:Wilson (2014 2095: 2083: 2075: 2070: 2058: 2046: 2034: 2022: 2010: 2002: 1994: 1983: 1965:McKay (2012) 1961:F. G. (1854) 1956: 1944: 1936: 1931: 1913: 1909: 1884: 1865: 1854:Thomas (1998 1849: 1837: 1825: 1818:Swart (1980) 1813: 1800: 1714: 1701:Lie algebras 1695: 1681: 1677: 1673: 1669: 1667: 1650: 1623:Interactive 1605:Möbius strip 1587:Klein bottle 1585:A 6-colored 1547:Borodin 1984 1543:Borodin 1984 1531:Möbius strip 1528: 1522:such as the 1511: 1507: 1501: 1493:Klein bottle 1474: 1397: 1391: 1384: 1307: 1293: 1267: 1263: 1252: 1217: 1209: 1199: 1188: 1172: 1165: 1161: 1157: 1119: 1117: 1108:reducibility 1104: 1102: 1098: 1093: 1089: 1087: 1012: 1005: 1000: 996: 992: 988: 984: 980: 976: 974: 969: 965: 961: 957: 953: 951: 941: 939: 934: 926: 922: 918: 916: 903: 899: 895: 891: 887: 883: 879: 875: 873: 868: 867:≤ 0 for all 864: 862: 693: 689: 684: 680: 676: 672: 668: 664: 660: 656: 648: 644: 640: 636: 632: 630: 620:triangulated 618: 616: 607: 605: 585: 572: 568: 557:Robin Thomas 553:Paul Seymour 542: 532: 522: 511: 503: 491: 484: 473: 466: 462:John A. Koch 447: 435: 419: 408: 401: 385:Alfred Kempe 382: 377: 372: 357: 355: 349: 345: 342: 322: 276:graph theory 273: 260: 256: 254: 209:; e.g., the 188: 184: 122:planar graph 116: 99: 84: 59: 55: 51: 45: 3538:Tait, P. G. 3152:Reed, Bruce 2799:: 159–175, 2789:Gethner, E. 2039:Tait (1880) 1725:Kenneth May 1676:colors, or 1535:Tietze 1910 1270:-colorable 1191:NP-complete 970:unavoidable 931:Kempe chain 529:magnum opus 514:RWTH Aachen 442:discharging 282:that has a 227:Kaliningrad 221:as part of 213:as part of 48:mathematics 3648:Categories 3194:Ringel, G. 3182:Ringel, G. 3174:2011-07-11 3098:2001-08-05 2813:1050.05049 2426:References 1916:(7): 257, 1832:, 216–222. 1518:: certain 1394:orientable 1276:Kurt Gödel 1195:complexity 1168:transitive 559:created a 495:microfiche 223:Azerbaijan 219:Nakhchivan 3626:EMS Press 3563:(2014) , 3495:: 155–159 3031:1201.2852 2919:: 133–143 1988:: 501–503 1499:in 1934. 1355:χ 1349:− 1202:cubic map 1106:immersion 1051:− 1025:∑ 826:− 800:∑ 763:∑ 759:− 729:∑ 713:− 586:In 2005, 420:In 1943, 329:Frederick 233:with its 200:connected 191:pie chart 167:≤ 155:χ 54:, or the 3483:(1910), 3470:(1995), 3457:archived 3434:(1998), 3389:17836752 3295:14962541 3238:16591648 3184:(1974), 3141:archived 3020:(2012), 2898:archived 2871:(2008), 2858:archived 2847:(2005), 2571:(1989), 1882:(1986), 1739:See also 1601:Tietze's 1537:) as do 1454:⌋ 1420:⌊ 1366:⌋ 1332:⌊ 1300:cylinder 1206:Missouri 975:Because 631:Suppose 207:exclaves 196:enclaves 119:loopless 60:Adjacent 3628:, 2001 3583:3235839 3548:: 729, 3531:1725004 3453:1633714 3425:0602826 3417:2321855 3359:Bibcode 3351:Science 3336:1441258 3287:1427555 3206:Bibcode 3125:Bibcode 3073:0214501 3036:Bibcode 2989:2369235 2958:3647828 2894:2463991 2824:Involve 2805:2050581 2766:1633950 2730:1799998 2698:0832128 2682:0465921 2658:2103049 2650:1466574 2609:8735627 2601:1025335 2546:Bibcode 2527:0543793 2490:0543792 2453:0535003 2366:3930641 2303:1217995 2001:(1960) 1686:cuboids 882:. Then 876:minimal 577:quartic 456:at the 366: ( 302:History 64:theorem 3597: 3581: 3571: 3529: 3519: 3451: 3423: 3415: 3387: 3377: 3334: 3293: 3285: 3275: 3236: 3229:225066 3226: 3071: 2987: 2956: 2892: 2811: 2803: 2764: 2754: 2728: 2696: 2680: 2656: 2648: 2607: 2599: 2589: 2525: 2488: 2451: 2441: 2364: 2354: 2301: 2291: 1903:& 1896: 1890:p. 116 1871:Möbius 1729:Alaska 1296:sphere 1214:Nevada 677:degree 639:, and 555:, and 415:planar 292:planar 284:vertex 239:Alaska 237:, and 231:France 215:Angola 143:, its 66:to be 50:, the 3460:(PDF) 3439:(PDF) 3413:JSTOR 3291:S2CID 3144:(PDF) 3113:(PDF) 3026:arXiv 2985:JSTOR 2954:JSTOR 2901:(PDF) 2876:(PDF) 2861:(PDF) 2854:(PDF) 2782:: 726 2726:JSTOR 2654:S2CID 2628:arXiv 2605:S2CID 1804:From 1793:Notes 1516:sharp 1504:torus 1304:genus 1239:torus 898:from 581:snark 411:snark 72:proof 3595:ISBN 3569:ISBN 3517:ISBN 3385:PMID 3375:ISBN 3273:ISBN 3234:PMID 2752:ISBN 2587:ISBN 2439:ISBN 2419:, 2. 2352:ISBN 2289:ISBN 1894:ISBN 1703:and 1487:and 1282:for 1152:map. 985:ring 692:and 590:and 452:and 368:1879 346:line 288:edge 203:open 93:and 78:was 3637:on 3550:doi 3509:doi 3405:doi 3367:doi 3355:202 3322:doi 3265:doi 3224:PMC 3214:doi 3133:doi 3059:doi 3005:doi 2977:doi 2946:doi 2942:110 2832:doi 2809:Zbl 2797:164 2742:doi 2718:doi 2670:doi 2638:doi 2579:doi 2554:doi 2513:doi 2476:doi 2344:doi 2281:doi 2257:doi 1918:doi 1656:'s 1549:). 1298:or 1278:'s 1193:in 1073:12. 848:12. 671:− 2 647:= 3 596:Coq 472:An 350:are 147:is 46:In 3650:: 3624:, 3618:, 3579:MR 3577:, 3546:10 3544:, 3527:MR 3525:, 3515:, 3493:19 3491:, 3455:, 3449:MR 3441:, 3421:MR 3419:, 3411:, 3399:, 3383:, 3373:, 3365:, 3353:, 3345:; 3332:MR 3330:, 3312:; 3308:; 3304:; 3289:, 3283:MR 3281:, 3271:, 3255:; 3251:; 3247:; 3232:, 3222:, 3212:, 3196:; 3162:, 3158:, 3139:, 3131:, 3121:49 3119:, 3115:, 3086:, 3069:MR 3067:, 3053:, 3034:, 3024:, 3001:31 2999:, 2983:, 2971:, 2952:, 2940:, 2917:88 2915:, 2896:, 2890:MR 2886:55 2884:, 2878:, 2826:, 2807:, 2801:MR 2795:, 2776:, 2762:MR 2760:, 2750:, 2724:, 2712:, 2694:MR 2678:MR 2676:, 2652:, 2646:MR 2644:, 2636:, 2624:17 2622:, 2603:, 2597:MR 2595:, 2585:, 2567:; 2552:, 2536:; 2523:MR 2521:, 2509:21 2507:, 2499:; 2486:MR 2484:, 2472:21 2470:, 2462:; 2449:MR 2447:, 2392:; 2362:MR 2360:, 2350:, 2334:; 2299:MR 2297:, 2287:, 2253:30 2251:, 2219:; 2191:; 2169:^ 2130:^ 2115:^ 2106:; 1971:^ 1963:; 1912:, 1892:, 1860:). 1778:: 1660:. 1529:A 1440:48 1400:: 1389:. 1352:24 1346:49 1218:NV 1210:MO 1200:A 1110:. 949:. 663:+ 659:− 655:, 635:, 551:, 547:, 531:, 501:. 483:A 464:. 417:. 298:. 225:, 217:, 182:. 109:. 3552:: 3511:: 3407:: 3369:: 3361:: 3324:: 3267:: 3216:: 3208:: 3164:1 3135:: 3127:: 3076:. 3061:: 3055:3 3038:: 3028:: 3007:: 2979:: 2973:2 2948:: 2834:: 2828:2 2784:. 2744:: 2720:: 2714:1 2701:. 2672:: 2640:: 2630:: 2581:: 2556:: 2548:: 2515:: 2478:: 2407:. 2346:: 2317:. 2283:: 2259:: 2235:. 2223:. 2195:. 2125:. 2053:. 2041:. 2029:. 1920:: 1914:3 1844:. 1820:. 1682:n 1678:n 1674:n 1670:n 1512:p 1508:g 1458:. 1449:2 1443:g 1437:+ 1434:1 1429:+ 1426:7 1416:= 1413:p 1398:g 1370:, 1361:2 1341:+ 1338:7 1328:= 1325:p 1308:p 1268:k 1264:k 1216:( 1208:( 1090:v 1070:= 1065:i 1061:v 1057:) 1054:i 1048:6 1045:( 1040:D 1035:1 1032:= 1029:i 993:k 989:k 981:G 977:G 962:G 958:G 942:G 935:v 927:v 923:v 919:G 904:v 900:G 896:v 892:v 890:( 888:d 884:G 880:G 869:i 865:i 845:= 840:i 836:v 832:) 829:i 823:6 820:( 815:D 810:1 807:= 804:i 796:= 791:i 787:v 783:i 778:D 773:1 770:= 767:i 754:i 750:v 744:D 739:1 736:= 733:i 725:6 722:= 719:e 716:2 710:v 707:6 694:D 690:n 685:n 681:v 673:e 669:v 665:f 661:e 657:v 649:f 645:e 641:f 637:e 633:v 610:( 573:n 569:n 567:( 565:O 517:( 261:A 257:A 170:4 164:) 161:G 158:( 131:G 20:)

Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.

Index