15R. It does. These Kempe chains are shown in Figures 11(a) and 11(b), respectively.(a)(b)Figurell:Blue-yellow and blue-green Kempechains in the Heawood mapBecause the Heawood map contains these two Kempe chains, it follows byKempe'sproof that thismapdoesnot containared-vellowKempe chainbetweenthe two neighboring regions of R that are colored red and yellow and does not con-tain a red-green Kempe chain between the two neighboring regions of R that arecolored red and green. This is, in fact, the case. Figure 12(a) indicates all regionsthat can be reached by a red-yellow Kempe chain beginning at the red region thatborders R and that is not adjacent to the yellow region bordering R.Furthermore,Figure 12(b) indicates all regions that can be reached by a red-green Kempe chainbeginning at the red region that borders R and that is not adjacent to the greenregion bordering R.In thefinal step of Kempe's proof,the two colors within each Kempe chain areinterchanged resulting in a coloring of the Heawood map with four colors. This dou-ble interchange of colors is shown in Figure 12(c). However, as Figure 12(c) shows,this results in neighboring regions with the same color. Consequently, Kempe'sproof is unsuccessful when applied to the Heawood map, as colored in Figure 10.What Heawood had shown was that Kempe's method of proof was incorrect.Thatis, Heawood had discovered a counterexample to Kempe's technique, not to the FourColor Conjecture itself. Indeed, it is not particularly difficult to give a 4-coloring ofthe regions of the Heawood map so that every two neighboring regions are coloreddifferently.Other counterexamples to Kempe's proof were found after the publication ofHeawood's 1890 paper,including a rather simple example (see Figure 13)given in
15 R. It does. These Kempe chains are shown in Figures 11(a) and 11(b), respectively. ... .... ... ... ...... .... . ... . ............................ .. ......... . .. . .. ........ ... ..... . .. ........................... .. ...... ...................... .. ... .... .. . ... ...... ........... .................................... . . . ............................... ... .............. . ...... ... ..... ..... .............................. ...................................... .. ... .. ..... . ... ..... .... ... .. ... .. .. .. .... ..................... . ... .................. .......................................................................... ........... ............... ........................ ..................................................... . ... ... . .. .. .. . ..... .... . . ... .. ... .. ... .... . ...... .. . .. .. ... .. .. .. .. ... ... .. ...... .. . .. ... ... .. ... .. .. .. .............................. .. .............. .. .. . ................... ......................................... .. .. ..... ......................... ............................. . ...... ... ... ....... .. ... . . ............ .. .. .. ... ... .. . ............................................................................................................. ................... ....... .... ... ........................................................................................................ . ................. .. .. ....... . .. ... .. ... ... . ....... ... .. ... ......... .... .. .. .. . .. ... .. ... ................... ...... ...... ..... .. . ... ... .... .. .. .. .. .. .. . .. ... .... . . .................................... . ............................................... ................ ... .. .... .. .... ... ..... .......... . .............................. ............ ............. r b y g r b r g b y g y g R b (a) g ................ ......................... ... ..... .... ..... ..... ..... .... .. ......... ......... ........ .................... ....... ..... ... ... ..... ........ ..................... ... ... ... ... .. ... ... .. ... . ... .. .. .. .. .. ... ............... ........... . ... .. .... . .... ........ . .... ................. .................... . ... ... ... .. . ......................... .. ... .... ... .. .. .. .. .. ....... ....... . ... .... .. ... . ..... ..................... . ................. ............. ...... .. ... .. .. .. .. .. ... .. ..... .... ... ... .... ........ ...................... .............................................................. ............................................... ..................................................... . ......... .. ............... .. .... . ... .. .. .. ....... .. . .. .. .... .. .. .. .. .. .. .. .. .. ... .. . . ................ .. ... .... ...................... y y b g r r b r y . .. ..... ............... ... ... ..... ............ ........ ...................................... ...................................... ................... ............ ...................................... ............................ ..................................... ................................................. ................... .......................... . . . . . . ................ ...................................... .................... ........................ ........... ................... ........................... ....................... ........................ .......................... ............................ .......................... ............................. ............................ ........................... ............................ ......................... .............................. ..................................... ..................... ............... .................... ..... ......... ............ ......... .......... ............... ............ .......... . ...... . ...................... .. . .. .. .. .... ......... ..... ............ .... ........ ........ ............ ... ...... ........................................................ ..................... ........................ . ... ... .. .. ...... .......... ..... . . ... ... ... ..... ............ ...... ..... ... ... .. .................. ... .................... . . .......................................... ............................ . ................. ............................. ....................... .................... ........................ ...................... ........................ .................. ......................... ...... ........................... ................................. ................................. ........................................ .......................................... ...................................... ............................................. ....................................... ...................... ................ ... .. .. .. .. .... ... ...... ......... . ......... .................................................. .. ............. ... .... ... ... . ..... ... . ..... ............................. .. ......... .... .. ........ .. .. ...... . .. ........................... .. ....... .................... . .. ... .... .. ... ...... ........... .................................... . . . ............................... ... .............. . ...... ... ..... ...... .............................. ..................................... . . ... ... ..... . .. . ..... .... ... .. ... .. .. ..... ..................... . ... .............................................................................................. ........... . ............................................... ..................... ................... . ..... . ... .. . . .. ..... .. .......... ..... . . ... ... ... ..... ............ ...... ..... ... ... .. ................... .... .................... . . ....................................................................... . ................ . ... ..... .............. .. ... ... .. ............ ......... .. .. . ................... ........................................ .. .. ..... .......................... .............................. . ...... ... ... ....... .. ... . . ............ .. .. .. ... ... .. . ................................................................................ ........................... .................. ...... .... ... ........................................... ............................................................ . ................. .. .. ....... . ... .. ... .. .. . ........ ... .. ... ........ .... .. .. .. . .. ... .. ... .................. ...... ...... ..... .. . ... ... .... .. .. .. .. .. .. . .. ... .... . . .................................... .............. y g r b y g r b r g b y g y g R b (b) r ........................ ...................................................... . .. ... . .. .. .. . ..... .... . ... . .. ... . .. .. . ... . ...... .. . .. .. ... ... .. .. ... ... .. ...... .. . .. ... ... ... ... ... .. ........... ............. ................ ......................... ... ..... .... ..... ..... ..... ... .. ......... ......... ........ .................... ....... ..... ... ... ..... ........ ..................... ... ... ... ... .. .. ... .. ... .. .. .. .. .. .. .. ... .............. ........... .. .. .. .. .. . .... ........ . .... ................. .................... . ... ... ... ... . ..................... .. .. .. ... .... ... .. .. .. .. ........ ....... . ... .... .. ... . ..... .................... . ................. ............. ...... .. ... .. .. . .. ... ... .. ..... .... ... ... .... ........ ...................... ............................................................. ............................................... ...................................................... . ......... .. ................ .. .... . ... .. .. .. ....... .. . .. .. .... .. .. .. .. .. .. .. .. .. ... .. . . ................ .. ... .... ...................... y y b g r r b ...... ..................... . . .... .. ..... ......... ..... ............ .... ..... ...... ... ....... ......... ... ..... ......................................................... . . . . . . . ........ .. . .. .. ..................................... ...................... ...................... ................. ................ .............. ................ ................ ....................... .......... .................... ........................ ........... ......................... ...... ........................... ................................. ................................. ........................................ .......................................... ...................................... ............................................. ....................................... ............ ......... .......... ............... ............ ........................... ......................... ........................... .......................... ....................... .................. .................... . .................. ...................... ..... . . . . . . . . ........................ ..... ............. ............. . ........ ............ .......... ............................................. ............. ........................ ........................ .......................... ...................... ................ ..... .. ....... . . . . . . . . . . . ........................ .......................................... .................................................. Figure 11: Blue-yellow and blue-green Kempe chains in the Heawood map Because the Heawood map contains these two Kempe chains, it follows by Kempe’s proof that this map does not contain a red-yellow Kempe chain between the two neighboring regions of R that are colored red and yellow and does not contain a red-green Kempe chain between the two neighboring regions of R that are colored red and green. This is, in fact, the case. Figure 12(a) indicates all regions that can be reached by a red-yellow Kempe chain beginning at the red region that borders R and that is not adjacent to the yellow region bordering R. Furthermore, Figure 12(b) indicates all regions that can be reached by a red-green Kempe chain beginning at the red region that borders R and that is not adjacent to the green region bordering R. In the final step of Kempe’s proof, the two colors within each Kempe chain are interchanged resulting in a coloring of the Heawood map with four colors. This double interchange of colors is shown in Figure 12(c). However, as Figure 12(c) shows, this results in neighboring regions with the same color. Consequently, Kempe’s proof is unsuccessful when applied to the Heawood map, as colored in Figure 10. What Heawood had shown was that Kempe’s method of proof was incorrect. That is, Heawood had discovered a counterexample to Kempe’s technique, not to the Four Color Conjecture itself. Indeed, it is not particularly difficult to give a 4-coloring of the regions of the Heawood map so that every two neighboring regions are colored differently. Other counterexamples to Kempe’s proof were found after the publication of Heawood’s 1890 paper, including a rather simple example (see Figure 13) given in
16CHAPTER0.THEORIGINOFGRAPHCOLORINGS(a)(b)(c)Figure12:StepsinillustratingKempe'stechnique1921byAifred Errera (1886-1960),a student ofEdmund Landau, well known forhis work in analytic number theory and the distribution of primes.Figure 13:The Errera exampleIn addition to the counterexample to Kempe's proof, Heawood's paper containedseveral interesting results, observations, and comments.For example, althoughKempe's attempted proof of the Four Color Theorem was incorrect, Heawood wasable to use this approach to show that the regions of every map could be coloredwith five or fewer colors so that neighboring regions were colored differently (seeChapter 8).Heawood also considered theproblem of coloringmapsthat can be drawn onother surfaces. Maps that can be drawn in the plane are precisely those maps
16 CHAPTER 0. THE ORIGIN OF GRAPH COLORINGS ................................................ .. ............. ... .... ... ... . ..... ... . .... . ............................. .. ......... .... .. ........ .. .. ...... . .. ........................... .. ....... .................... . .. ... .... .. .. ...... ........... .................................... . . .. .............................. ... ............... . ..... ... ..... ...... .............................. ..................................... . . ... ... ..... . .. . ..... .... ... .. ..... .. ..... ..................... . ... .............................................................................................. ........... .............. ........................ ...................................................... . .. ... . .. .. .. . ..... .... . ... . . ......... . ......... .. . ................ . ... ..... .............. .. ... ... .. ............ ......... .. .. . ................... ........................................ .. .. ..... .......................... .............................. . .. .. ... ... ... ....... .. ... . . ............ .. .. .. ... ... .. . ................................................................................. ........................... .................. ...... .... ... ........................................... ............................................................ . ................. .. .. ....... . ... .. ... .. .. . ........ ... .. ... ......... ... .. .. .. . .. ... .. ... .................. ...... ...... ..... .. . ... ... .... .. ...... .. .. . .. .. . .... . . .................................... . ............................................... ................ ... .. .. .. .. .... ... ...... . .. ... . .. . .. ... . ...... .. . .. . .. .. ... .. .. ... ... .. ...... .. . .. ... ... ... ... ... .. r b g b r g b y g y g R b (a) y r y g ........... ............. ................ ......................... ... ..... .... ..... ..... ..... ... .. ......... ................. .................... ....... ..... ... ... ..... ....... ...................... ... ... ... ... ... .. .. . .... . ........ .. .. . .. ... ........... ........... .. .. .. . ... . .... ........ . .... ................. .................... . ... ... ... ... . ......................... .. ... .... ... ................ ....... . ... .. . .. .. .. . ..... .................... . ................. ............. ...... .. ... . ... . .. ... ... .. ..... .... ... ... .... ........ ....................... .............................................................. ............................................... ...................................................... . ......... .. ............... .. .... . ... .. .. .. ....... .. . .. .. .... .. .. .. .. .. .. .. ... ... ... . . ................ .. ... .... ...................... y y b g r r b r . ....................................................................... ............ ...................................... ............................ ..................................... ................................................. . . . . . . ................ ..................... ....................... .................... ........................ ...................... ........................ ................... ................... ........................... ....................... ........................ .......................... ............................ .......................... ............................. ............................ ........................... ............................ ......................... .............................. ..................................... ...................................... ...................................... ...................................... .................. . . . . . . . . ........................ ......................... . ....... .... ..................... ...... ..................... . . .... .. ..... ......... ..... ............ .... ..... ...... ... ....... ......... ... ..... ......................................................... ..................... ................... . ..... .... .. . . .. ..... .. .......... ..... . . ... ... .... ..... ............ ...... ..... ... ... .. .. .. ............... .... .................... . . ..... . ................. ............................ .................................... ..................................... .......... .......... ......................................... ...................... ................ . . . .. . . . . . . . . . . . . . . . . . . . ................ ..... ........................ ....................... ...................... ......... ................ .... . .... .. ... ... ..... . ......... . ......... ................................................. .. ............. ... .... ... ... .. .... ... . ... .. ............................. .. ......... . .. .. .. ........ .. .. ..... .. ........ .................. .. ....... ...................... .. ... .... ... .. ..... ............ .......................... ......... . . . .. .. ............................ ... ............... . .. ... ... ..... ..... ............................. ....................................... . ... ... .. ... . ... ..... .... ... .. ... .. .. ........................... . ... ............................................................................................ .. ............ . ............................................. ..................... ........................ .... ... . . .. ..... .. .......... ..... .. . ... ... .... .... ............ ...... .... ... ... .. .................. ... .................... . . ....................................................................... . ................. . .... ................ .... ... ... .. ............ ........ . ... . ................... ...................................... .. .. ..... ........................... ............................. . . .. ..... ... ...... ... ... .. . ............ .. .. .. ... ... .. . .............................................................................. . ... ............................ ................... ....... .... ... ...................................................................................................... . ................. .. .. ....... . ... .. ... .. .. ....... ... .. ... ......... ... .. .. .. . .. ... .. ... ................. ...... ...... ..... ... .. ... ... .... .. .. .. .. .. .. .. . .. . .. .. . . .................................... ............... y g r b y g r b r g b y g y g R b (b) r ........................ ...................................................... . .... ... .. ... .. . ..... .... . .... .. .. .. .. .. .... . ...... .. . .. .. ... .. .. .. .. ... ... . ....... .. . .. ... .. ... .. ... .. ............ .............. ................ ......................... ... .... .... ..... ..... ..... ..... ......... ................. .................. ....... .... .... ... .... ...... .......... ................... ... ... ... .. .... .. ... . ... .. ..... .. .. .. ... ... ........... ......... .. . ... . .. ... . .... .......... ... ................. .................... . ... ... ... .. . ....................... .. .. ... .... ... .. .. .. ........... ....... .... .... .. ... . ..... ..................... . ................. ............. ...... .. ... .. .. .. .. .. ... .. ...... .... ... .. ..... ........ ....................... ............. ................................................. ................................................ ...................................................... . ......... .. ................ .. .... . ... .. .. .. ....... .. . .. .. .... .. .. .. .. .. .. .. .. .. ... .. . . ................ .. .. .... ...................... y y b g r r b ...... ........................ .. .. . .... ......... ..... ............ .... ..... ..... ... ....... .......... ... ..... ....................................................... .. . . . . . . . . . . ........................ .......................................... .................................................. .............................................. ......................... ........................... ......................... ....................... .... ... ........ . . . . . . ...................................... ...................... ...................... ................. ................ .............. ................ ................ ....................... ........................... ............. ........................ ....................... .......................... ...................... ............... .... ... .................. . . . . . . . . . . . . . . . . . . . . . . . .. . . .................... . .................. ...................... ..... . . . . . . . . ........................ ..... ............. ............. ....... .................... ..... .................... .......... ............................ .......................... ................ ............... . . . . . g b y b b y b . ................ . .. ............................ . ................................. ................................................. ............................................... ...................................................... . ....... .. .. ................ .. .. .. . .... .. .. .. ....... .. . .. .. ..... .. . .. .. .. .. .. .. ... ... .. . . ................. ............. ...... .. ... .. . .. .. . .. ... .. .... .... ... ... .... ......... ...................... .. .. ... .... .. ... .. .. ......... ........ . ... . ... .. .. .. . ........................... ........... ......... . ... ... ... ... . . . ... .. .. . .. .. ... .. .. .. .. .. . ............. ......... . .. ... .. ... ..... ........... ................. .... .... .... .... ..... ..... .... .... ........ ...... ........ .... ............... ...... ....... ..... ... .... ...... .......... ................... ... ... ..... ... ................ ........................... ............ .............. .. ... . .. ... .... . ...... . ... .. .. ... .. .. .. ... . ... ....... .. . .. .. ... ... .. ... . ........................ ...................................................... . ... .. .. . .. . ... . ..... .... . .... . b g y g r r (c) r y r g g g r r R g b y ............... . ............... .. .. .. ..... . . .. ... . ... .. .. ....... .... ... .... ........ .. .. .. .. .. . ... .. ... ................ ...... ...... ..... .... ........................................................................................... ....... .... ... ........... .................. .......... ............................. . ......................... .............................................. .. ... ... ... .. .. . . . .. ..... ... ........ .. ... .. . ............ ............................. ........................... . ... . .................. ...................................... .. .. ..... . ... ...... .............. .. ... ... .. ........... ........ . ................. . ........................................................................ . ... ... .. .... ........... ...... ..... ... .... ................. ... .................... . . .................... ....................... .. .. . ... . . .. ..... .. ......... .. .... .. ...... ........................ .. . .. ..... .......................... ... ...... ....... ...... ........... ... .... ...................................................... .. ... ... .. .. .. .. .... .. .. .. . .. . ... . . .................................... ......................................................... .. ............. ..... .... ... .. ... .. .... ... ..................... . ... .................................. . .. ... .. . ... .. . .. . ............................. ....................................... ............... . .. . .. ... .... ...... . .. ............................... ... .............................. ........ .. .... ....................... .. .... ... .. .. ......... .. ........ ........................... . .. ....... .. .. ... .. .. ...... . .... . .... .... ... .. .. .... ... . ... .. ............................ .............................. .. ............. ................... .......... . ......... . ................... ... .... .. ... ... ..... . . ............................................ Figure 12: Steps in illustrating Kempe’s technique 1921 by Alfred Errera (1886–1960), a student of Edmund Landau, well known for his work in analytic number theory and the distribution of primes. . r r R r g y y g b r y g b g y b . . .. .... ........ ................... .... ... ........................................ . . .. .. ... .... .... ....... ........ ............... .............. ............ ........ ....... ..... .... ... .. .. . . ....................................................................................................... . . . .. .. .. ... .... .... ..... ..... ...... ....... ....... ......... ........... ..... ................. ................ ..... ............ ........... ......... ........ ....... ..... ...... ..... ... .... ... .. .. .. .. . . ................................................................................................................................................................................................ . . . . .. .. ... ... .... .... ..... ....... ........ ......... ............... ................. ...... ...... ..... .... ......... ........ ....... ...... .... .... .... .. .. .. .. . ....................................................................................................................................................... . . . . . . . . . ...... .............................. ..................... . . . . . . ................. ................................ ......... .............................................. .................................... ........................... .. . . . Figure 13: The Errera example In addition to the counterexample to Kempe’s proof, Heawood’s paper contained several interesting results, observations, and comments. For example, although Kempe’s attempted proof of the Four Color Theorem was incorrect, Heawood was able to use this approach to show that the regions of every map could be colored with five or fewer colors so that neighboring regions were colored differently (see Chapter 8). Heawood also considered the problem of coloring maps that can be drawn on other surfaces. Maps that can be drawn in the plane are precisely those maps
17that can be drawn on the surface of a sphere.There are considerably more complexsurfaces on which maps can be drawn, however. In particular, Heawood proved thattheregions ofevervmap drawn on the surfaceof atorus canbe colored with seven orfewer colors and that there is, in fact.a map on the torus that requires seven colors(see Chapter 8).More generally, Heawood showed that the regions of every mapdrawn on a pretzel-shaped surface consisting of a sphere with k holes (k > O) canbe colored with7+V+48kcolors. In addition, he stated that such maps requiringthis number of colors exist.He never proved this latter statement, however. In fact,it would take another 78 years to verify this statement (see Chapter 8).Thus the origin of a curious problem by the young scholar Francis Guthrie wasfollowed over a quarter of a century later bywhat was thought to be a solutiontotheproblembyAlfredBrayKempe.However,weweretolearnfromPercyJohn Heawood a decade later that the solutiowas erroneous,whichreturned theproblemto its priorstatus.Well notquite-asthese eventsproved tobe steppingstones along the path to chromatic graph theory.Is it five?Is it four?Heawood rephrased the query.Sending us back to before,But moving forward a theory.At the beginning of the 20th century,the Four Color Problem was still unsolved.Although possibly seen initially as a rather frivolous problem, not worthy of a seriousmathematician's attention, it would become clear that the Four Color Problem wasa very challenging mathematics problem.Many mathematicians, using a variety ofapproaches,would attackthisproblemduringthe1900s.Asnoted,itwasknownthat if the Four Color Conjecture could be verified for cubic maps, then the FourColor Conjecture would be true for all maps. Furthermore, every cubic map mustcontain a region surrounded by two,three,four,or five neighboring regions.Thesefour kinds of configurations (arrangements of regions)were called unavoidable be-cause every cubic map had to contain at least one of them. Thus the arrangementsof regions shown in Figure14 makeup an unavoidable set of configurations.Figure14:An unavoidable set of configurations in a cubicmapA region surrounded by k neighboring regions is called a k-gon. It is possibleto show that any map that contains no k-gon where k < 5 must contain at least
17 that can be drawn on the surface of a sphere. There are considerably more complex surfaces on which maps can be drawn, however. In particular, Heawood proved that the regions of every map drawn on the surface of a torus can be colored with seven or fewer colors and that there is, in fact, a map on the torus that requires seven colors (see Chapter 8). More generally, Heawood showed that the regions of every map drawn on a pretzel-shaped surface consisting of a sphere with k holes (k > 0) can be colored with j 7+√ 1+48k 2 k colors. In addition, he stated that such maps requiring this number of colors exist. He never proved this latter statement, however. In fact, it would take another 78 years to verify this statement (see Chapter 8). Thus the origin of a curious problem by the young scholar Francis Guthrie was followed over a quarter of a century later by what was thought to be a solution to the problem by Alfred Bray Kempe. However, we were to learn from Percy John Heawood a decade later that the solution was erroneous, which returned the problem to its prior status. Well not quite – as these events proved to be stepping stones along the path to chromatic graph theory. Is it five? Is it four? Heawood rephrased the query. Sending us back to before, But moving forward a theory. At the beginning of the 20th century, the Four Color Problem was still unsolved. Although possibly seen initially as a rather frivolous problem, not worthy of a serious mathematician’s attention, it would become clear that the Four Color Problem was a very challenging mathematics problem. Many mathematicians, using a variety of approaches, would attack this problem during the 1900s. As noted, it was known that if the Four Color Conjecture could be verified for cubic maps, then the Four Color Conjecture would be true for all maps. Furthermore, every cubic map must contain a region surrounded by two, three, four, or five neighboring regions. These four kinds of configurations (arrangements of regions) were called unavoidable because every cubic map had to contain at least one of them. Thus the arrangements of regions shown in Figure 14 make up an unavoidable set of configurations. .................................... ...................................... . ............ . . .............................................. ......................................... ..... .. .......... . . . . . . . . . . . . . . . . . . . ... ... .... ..... ......... ... . ...... ...... .... ....... .... ....... ... .... .. .. . . . . . . . . . ...... .......... .......... .......... .......... .......... ......... ...... . . . . . . . . .. .. . .... .... ........ .. .. ...... .... ...... ........ .... ...... .... ... ... .. . . . . . . . ...... ......... .......... .......... .......... .......... .......... ...... . . . . . . . . . ... .. . .... ..... ........ .. .. ...... .... ...... ........ .... ...... .... .... ... .. . . . . . . . . . ...... .......... .......... .......... .......... .......... ......... ...... .. . . . . .. ...... ............. ... . ........................ . . . . .. .. . .... .... ........ ... .. ...... ..... ..... ....... .... ...... ... ... ... .. . . . . . . . ...... ......... .......... .......... .......... .......... .......... ...... . . . . . .. ............................. ..................................... Figure 14: An unavoidable set of configurations in a cubic map A region surrounded by k neighboring regions is called a k-gon. It is possible to show that any map that contains no k-gon where k < 5 must contain at least
18CHAPTER0.THEORIGINOFGRAPHCOLORINGStwelve pentagons (5-gons).In fact, there is a map containing exactly twelve regions,each of which is a pentagon. Such a map is shown in Figure 15, where one of theregions is the “exterior region". Since this map can be colored with four colors, anycounterexample to the Four Color Conjecture must contain at least thirteen regions.Aifred Errera proved that no counterexample could consist only of pentagons andhexagons (6-gons).Figure15:AcubicmapwithtwelvepentagonsA reducible configuration is any configuration of regions that cannot occur ina minimum counterexampleof theFour Color Conjecture.Manymathematicianswho attempted to solve theFour Color Problem attempted to do so by trying tofind an unavoidable set S of reducible configurations.Since S is unavoidable,thismeans that every cubicmapmust containat least oneconfiguration in S.Becauseeach configuration in S is reducible, this means that it cannot occur in a minimumcounterexample. Essentially then, a proof of the Four Color Conjecture by thisapproachwouldbeaproofbyexampleresultinginanumberofmnmintercases (one case for each coonfiguration in theunavoidableset S)where each caseleadstoa contradiction (that is.each configuration isshowntobereducible)navoidable set shown inFigure14thatSince the onlyconfiguration in theucould not be shown to be reducible was the pentagon, this suggested searching formore complex configurations that must also be part of an unavoidable set withthe hope that these more complicated configurations could somehow be shown tobe reducible.For example, in 1903 Paul Wernicke proved that every cubic mapcontaining no k-gon where k<5must either contain two adjacentpentagons ortwo adjacent regions, one of which is a pentagon and the other a hexagon (seeChapter 5).That is, the troublesome case of a cubic map containing a pentagoncould be eliminated andreplaced bytwo different cases.Finding new, large unavoidable sets of configurations was not a problem. Find-ing reducible configurations was.In 1913 the distinguished mathematician GeorgeDavid Birkhoff (1884-1944)published a paper called The reducibility of maps inwhich he considered rings of regions for which there were regions interior to as wellas exterior to the ring. Since the map was a minimum counterexample,the ring to-gether with the interior regions and the ring together with the exterior regions couldboth be colored with four colors. If two 4-colorings could be chosen so that theymatch along the ring, then there is a 4-coloring of the entire map. Since this canalways be done if the ring consists of three regions, rings of three regions can neverappear in a minimum counterexample.Birkhoff proved that rings of four regionsalso cannot appear in a minimum counterexample. In addition, he was successful
18 CHAPTER 0. THE ORIGIN OF GRAPH COLORINGS twelve pentagons (5-gons). In fact, there is a map containing exactly twelve regions, each of which is a pentagon. Such a map is shown in Figure 15, where one of the regions is the “exterior region”. Since this map can be colored with four colors, any counterexample to the Four Color Conjecture must contain at least thirteen regions. Alfred Errera proved that no counterexample could consist only of pentagons and hexagons (6-gons). . . ... ....... ........... ........ ..... ... .. ........................................ . . .. ... .... ...... ....... ................... ............ ............ ...... .... ... .... . ................................................................................ . . .. .. ... .... .... ..... ....... ........ ............. ................... ........ ....... ......... ....... ...... .... .... ... .. .. . ....................................................................................................................... . .............................. ............................... .. . . ... ... . .......... ............................ .................... . .. . .. . . . Figure 15: A cubic map with twelve pentagons A reducible configuration is any configuration of regions that cannot occur in a minimum counterexample of the Four Color Conjecture. Many mathematicians who attempted to solve the Four Color Problem attempted to do so by trying to find an unavoidable set S of reducible configurations. Since S is unavoidable, this means that every cubic map must contain at least one configuration in S. Because each configuration in S is reducible, this means that it cannot occur in a minimum counterexample. Essentially then, a proof of the Four Color Conjecture by this approach would be a proof by minimum counterexample resulting in a number of cases (one case for each configuration in the unavoidable set S) where each case leads to a contradiction (that is, each configuration is shown to be reducible). Since the only configuration in the unavoidable set shown in Figure 14 that could not be shown to be reducible was the pentagon, this suggested searching for more complex configurations that must also be part of an unavoidable set with the hope that these more complicated configurations could somehow be shown to be reducible. For example, in 1903 Paul Wernicke proved that every cubic map containing no k-gon where k < 5 must either contain two adjacent pentagons or two adjacent regions, one of which is a pentagon and the other a hexagon (see Chapter 5). That is, the troublesome case of a cubic map containing a pentagon could be eliminated and replaced by two different cases. Finding new, large unavoidable sets of configurations was not a problem. Finding reducible configurations was. In 1913 the distinguished mathematician George David Birkhoff (1884–1944) published a paper called The reducibility of maps in which he considered rings of regions for which there were regions interior to as well as exterior to the ring. Since the map was a minimum counterexample, the ring together with the interior regions and the ring together with the exterior regions could both be colored with four colors. If two 4-colorings could be chosen so that they match along the ring, then there is a 4-coloring of the entire map. Since this can always be done if the ring consists of three regions, rings of three regions can never appear in a minimum counterexample. Birkhoff proved that rings of four regions also cannot appear in a minimum counterexample. In addition, he was successful
19in proving that rings of five regions cannot appear in a minimum counterexampleeither - unless the interior of the region consisted of a single region.This gen-eralized Kempe's approach.While Kempe's approach to solving the Four ColorProblem involved the removal of a single region from a map,Birkhoff's method al-lowed the removal of regions inside or outside some ring of regions.For example, aconfiguration that Birkhoff was able to prove was reducible consisted of a ring of sixpentagons enclosing four pentagons. This became known as the Birkhoff diamond(see Figure 16).Figure16:TheBirkhoff diamond (a reducible configuration)Philip Franklin (1898-1965)wrote his doctoral dissertation in1921titled TheFourColor Problemunder thedirection of Oswald Veblen (1880-1960).Veblenwas the first professor at the Institute for Advanced Study at Princeton University.He was well known for his work in geometry and topology (called analysis situsat the time) as well as for his lucid writing. In his thesis, Franklin showed thatif a cubic map does not contain a k-gon, where k < 5, then it must contain apentagon adjacent to two other regions, each of which is a pentagon or a hexagon(see Chapter 5).This resulted in a larger unavoidable set of configurations.In1922Franklin showed thateverymapwith 25orfewer regionscould be coloredwith four or fewer colors.This number gradually worked its way up to 96 in a resultestablished in 1975 by Jean Mayer, curiously a professor of French literature.Favorable impressions of new areas ofmathematics clearly did not occurquickly.Geometry of course had been a prominent area of study in mathematics for cen-turies. The origins of topology may only go back to 19th century however. In his1927 survey paper about the Four Color Problem, Alfred Errera reported that somemathematicians referred to topology as the"geometry of drunkards". Graph theorybelongs to the more general area of combinatorics.While combinatorial argumentscan be found in all areas of mathematics, there was little recognition of combina-torics as a major area of mathematics until later in the 20th century, at which timeIndeed,John Henry ConstantineWhiteheadtopologywasgaininginp(1904-1960),one of thefounders of homotopytheory in topology,reportedly saidthat "Combinatorics is the slums of topology."However, by the latter part of the20th century,combinatorics had come into its own.Thefamous mathematicianIsrail Moiseevich Gelfand (born in 1913) stated (in 1990):The older I get, the more I believe that at the bottom of most deepmathematical problems there is a combinatorial problem.Heinrich Heesch (1906-1995)was a German mathematician who was an assistant
19 in proving that rings of five regions cannot appear in a minimum counterexample either – unless the interior of the region consisted of a single region. This generalized Kempe’s approach. While Kempe’s approach to solving the Four Color Problem involved the removal of a single region from a map, Birkhoff’s method allowed the removal of regions inside or outside some ring of regions. For example, a configuration that Birkhoff was able to prove was reducible consisted of a ring of six pentagons enclosing four pentagons. This became known as the Birkhoff diamond (see Figure 16). . . .. .... ...... ......... .............. ....... ...... ...... .... ... .. ............................................................... . . .. .. .... ..... ...... ....... ........... ................... .......... ......... ....... ...... ..... .... .. .... . ..................................................................................................... . ..................... ...................... ..... ....................... ............... Figure 16: The Birkhoff diamond (a reducible configuration) Philip Franklin (1898–1965) wrote his doctoral dissertation in 1921 titled The Four Color Problem under the direction of Oswald Veblen (1880–1960). Veblen was the first professor at the Institute for Advanced Study at Princeton University. He was well known for his work in geometry and topology (called analysis situs at the time) as well as for his lucid writing. In his thesis, Franklin showed that if a cubic map does not contain a k-gon, where k < 5, then it must contain a pentagon adjacent to two other regions, each of which is a pentagon or a hexagon (see Chapter 5). This resulted in a larger unavoidable set of configurations. In 1922 Franklin showed that every map with 25 or fewer regions could be colored with four or fewer colors. This number gradually worked its way up to 96 in a result established in 1975 by Jean Mayer, curiously a professor of French literature. Favorable impressions of new areas of mathematics clearly did not occur quickly. Geometry of course had been a prominent area of study in mathematics for centuries. The origins of topology may only go back to 19th century however. In his 1927 survey paper about the Four Color Problem, Alfred Errera reported that some mathematicians referred to topology as the “geometry of drunkards”. Graph theory belongs to the more general area of combinatorics. While combinatorial arguments can be found in all areas of mathematics, there was little recognition of combinatorics as a major area of mathematics until later in the 20th century, at which time topology was gaining in prominence. Indeed, John Henry Constantine Whitehead (1904–1960), one of the founders of homotopy theory in topology, reportedly said that “Combinatorics is the slums of topology.” However, by the latter part of the 20th century, combinatorics had come into its own. The famous mathematician Israil Moiseevich Gelfand (born in 1913) stated (in 1990): The older I get, the more I believe that at the bottom of most deep mathematical problems there is a combinatorial problem. Heinrich Heesch (1906–1995) was a German mathematician who was an assistant