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:
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:
324:
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
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
113:Formulation
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.