10CHAPTER 0.THE ORIGIN OF GRAPH COLORINGSFigure6:Ayellow-red Kempechain inthemapMthat can be reached by a green-red Kempe chain beginning at Rs.Upon doing this.ing of all regions in M (except R) is obtained, in which each neighboringa 4-coloregion of R is colored red, blue, or yellow. We can then color R green to produce a4-coloring of the entire map M. We may therefore assume that Rs can be reachedby a green-red Kempe chain that begins at Rs. (See Figure 7.)RRR3Figure 7: Yellow-red and green-red Kempe chains in the map MBecause there is a ring of regions consisting of R and a green-red Kempe chain,there cannot bea blue-yellowKempe chain in M beginning at Ry andending at RrIn addition,because thereisaring of regions consisting of R and a yellow-red Kempechain, there is no blue-green Kempe chain in M beginning at R2 and ending at Rs.Hence we interchange the colors blue and yellow for all regions in M that can bereached by ablue-yellow Kempe chain beginning at Ry and interchange the colors
10 CHAPTER 0. THE ORIGIN OF GRAPH COLORINGS . . . . . . ....... ....... ....... ...... ...... ....... ...... ...... ....... ....... ... .... .... ................... .......... ........... ........... ........... ........... .. ...................................... ............................................ .. .. ... ....... ......................... ....... ..... .................................................................................. ................................... . . . .. ... ... ... ........... .... ... .. . ... .... ..... ...... ....... ................. .. ... ...... ......... ................. ...... ..... .... .. .. ......... .. .... .......... ... . . ... .. .. .... ........ .... ............................ ............... . ... ..... ...... .......... ....... ..... ... .................................... . . ................................. . ..... .... .. ..... ... ... ...... ..... ... ... . ... ... .. ........................................................ . ...................................................... ...................................................................................................................... .. . .. .. .. .. .. .................................................. .... ... .. ... .... ... ..... .......... ...... ..... ... .. ... ..... ...... ........... ....... .... .......... . .. ... ... ... .. .. ... .. ..... .. .. ... .. .. ..... . ...... . .. . .. ............................. ...................... ........................................................................................................ ...................................... .. .... ... ... .... ..... ....... ......... ....... ................ ............... ... .... ... ... .. .. ... . ....................... ............... ...... ......... .............. ... ....... ....... .... .... ......... ... .... ............ ...... ..... ... .. . .. . .................. .............. ........................... .. ..................................... . ....... ....... ...... ...... ..... .... ... ... .. . ..... . . ..... .. ... ....... .. ... .. .................................................................. .... ... ... ......................... . ............ .. ... ... ... . . ... ... .. .. . ....................................... ............................................. ......... .. .. ... . .. ... .................... ... ... ... .. .... ..... ......... ...... . .... .. ..................................................... ... .. ... .............................. .. .... .. ... .. ..... .................. .... ................. .......................... ........................ ............................ ................. ................................................... .......................... . ... .. .. .. .. R r r y y y r y r b g b R3 R4 R5 R1 R2 Figure 6: A yellow-red Kempe chain in the map M that can be reached by a green-red Kempe chain beginning at R5. Upon doing this, a 4-coloring of all regions in M (except R) is obtained, in which each neighboring region of R is colored red, blue, or yellow. We can then color R green to produce a 4-coloring of the entire map M. We may therefore assume that R3 can be reached by a green-red Kempe chain that begins at R5. (See Figure 7.) ...................................... .......... .................. ........... ...... ...... . ...... ...... ...... ...... ...... ...... ...... ...... ... ... ... ... .................... . . . . . . . . . .................................................................................... ................................. . . .. .. .. ... ... .... ........... .. ... . ... .... ..... ...... .......... .......... ... .. ... ....... ........ ............. ....... ....... ... ... ... .... . . .... .. .......... ... .. . ... .. .. .. .. ...... . ................. ............. ................ . .. ..... ...... ..... . ........... ..... ... ................................... . . . ................................ . ..... .... .. ..... ... ... ....... .... ....... . ... .. .. .. ..................................................... . ....................................................... ................................................... ............................................. ............... ....... .. .. .. ... .... . .......................................... . ...... ... .. ... .... .. .... ..... ........... ..... .... ... .. . .. .... ..... ........... ........ ... ....... .... . .. ... .... ... ... ... .. .. ...... .. .. ... .. .. .. ... . ... . . . .. . .. ............................... ....................... .......................................................................................................... .......... ......................... .. ... ... .... .... ..... ...... ................... ........... ................. ..... ... ... ... .. .. ... . ....................... ............... ...... ......... .............. ...... ...... .... ..... ........ ..... .... ............. ...... ..... ... .. .... .................. .............. ............................... .................................... . ....... ...... ....... ..... ..... ..... .... ... .. . ....... . ..... .. ... ....... .. ... .. ................................................................... ... ... . .. ....................... . .... .. ......... . . ... ... ... .. . ... ... .. .. ...................................... ............................................ .......... . . . ... .. ... ..................... . ... ... ... .. .... ..... ........ ....... . ... ... ................................................ .... .... .. ............................. . . . ..... ... ... ... .... .. ........ ....... .. .. ... ........... ...... .......................... ...................... . ........................... .................................................................... .......................... . ... ... ... .. ............................................................... ...... ........... . .... .. ... ...... .... ... .... ... .... ...... ... ................................................................................. .. ... ... ........ .. .......... . ... .................. ........ .. . . .. ..... .... ........ . . ......................... ................................. .. ..... .... . . ........................ ............... . ............................................................................................................... ..................................... . . . . .... .. ........ .... ... . .. .. .. ... ................ ... ... .. .. ........................................................................................... .. .... ....... ............... . .... ... .. .... ..... ........ . ... ......... ..... .... ........ ......... ....... .. ............................................................................ .... .. .. .. ... ........... .. ........................ . .. ....... ..... .... .... ... ... .............. ... .. .. .. ... ... ... .. .... .............. .. ................... .. .. .. .. .. .. ... .. . . ......... . . ............................................................................... .. . . . ..... ....... ... .......... ... .... ............... .. ... ..... ............ ... ... ....... ...... ..... .... ... .......... .. ... ......... ... .. ............. . ............ .. .. ... ...... ... ... ...... ... ... ...... .... ... ... ..... ................ .... y y g r r r r r y r g r g g b b y g R2 R r R4 R3 R5 R1 Figure 7: Yellow-red and green-red Kempe chains in the map M Because there is a ring of regions consisting of R and a green-red Kempe chain, there cannot be a blue-yellow Kempe chain in M beginning at R4 and ending at R1. In addition, because there is a ring of regions consisting of R and a yellow-red Kempe chain, there is no blue-green Kempe chain in M beginning at R2 and ending at R5. Hence we interchange the colors blue and yellow for all regions in M that can be reached by a blue-yellow Kempe chain beginning at R4 and interchange the colors
11blue and green for all regions in M that can be reached by a blue-green Kempechain beginning at R2. Once these two color interchanges have been performedeach of the five neighboring regions of R is colored red, yllow, or green. Then Rcan be colored blue and a 4-coloring of the map M has been obtained, completingthe proofAs it turned out, the proof given by Kempe contained a fatal flaw,but onethat would go unnoticed for a decade. Despite the fact that Kempe's attemptedproof of theFour ColorProblem was erroneous,he madeanumber of interestingobservations in his article. He noticed that if a piece of tracing paper was placedover a map and a point was marked on the tracing paper over each region of thewo points were joined by a line segment whenever the correspondingmaboundary, then a diagram of a "linkage""was produced.regionshadnonaomFurthermore, the problem of determining whether the regions of the map can becolored with focolors so that neighboring regionss are colored differently is theiningwhetherthepoinsinthelinkagecanbecoloredwithproblenfour colors so that every two points joined by a line segment are colored differently(See Figure 8.)Figure 8: A map and corresponding planar graplIn 1878 Sylvester referred to a linkage as a graph and it is this terminology thatbecame accepted. Later it became commonplace to refer to the points and lines ofa linkage as the vertices and edges of the graph (with "vertex" being the singularof "vertices"). Since the graphs constructed from maps in this manner (referred toas the dual graph of the map) can themselves be drawn in the plane without twoedges(linesegments)intersecting,thesegraphswere calledplanar graphs.Aplanargraph that is actually drawn in the plane without any of its edges intersecting iscalled a plane graph. In terms of graphs, the Four Color Conjecture could then berestatedThe Four Color Conjecture The vertices of every planar graph can be coloredwith four or fewer colors in such a way that every two vertices joined by an edgeare colored differently.Indeed, the vast majority of this book will be devoted to coloring graphs (notcoloring maps)and, in fact, to coloring graphs in general, not only planar graphs
11 blue and green for all regions in M that can be reached by a blue-green Kempe chain beginning at R2. Once these two color interchanges have been performed, each of the five neighboring regions of R is colored red, yellow, or green. Then R can be colored blue and a 4-coloring of the map M has been obtained, completing the proof. As it turned out, the proof given by Kempe contained a fatal flaw, but one that would go unnoticed for a decade. Despite the fact that Kempe’s attempted proof of the Four Color Problem was erroneous, he made a number of interesting observations in his article. He noticed that if a piece of tracing paper was placed over a map and a point was marked on the tracing paper over each region of the map and two points were joined by a line segment whenever the corresponding regions had a common boundary, then a diagram of a “linkage” was produced. Furthermore, the problem of determining whether the regions of the map can be colored with four colors so that neighboring regions are colored differently is the same problem as determining whether the points in the linkage can be colored with four colors so that every two points joined by a line segment are colored differently. (See Figure 8.) ....................................................... ... . .. .. .. ... ... ....... .......... ............ ........ .... ...... ..... .... . ... .. ................ .. ................. . ........................................................................................ ...... ........... . ... ... ... .... .... .... .................................. ........... .. ... . ... ... .. ... ... ............. ........... ........ .. .... ... ... ... ... ...................................... ...................... .............. .. .. . .................................. ...................................... . .. . ... . . ........... ............... ........................................... .. . .. ... . .. .. .. .. ... ... .... ..... ................................................. .. ....... . ..... ... .. ......... . .. ... ... ..... ............... .... ... .. .. .. . ........... ... . ......................... .................................................................... . . ... ... ... .. .. ... ....... .. ................................................................. .... ..... ..... ..... ..... ..... ..... .... ... ... .... .. ... .. .............. . ... .. .. ... ....... .. . ............................ .. .. .............................................................. . .. ... ... ... .. .. .. .. .. ........ ..................................................................................................... ....................................................... ... . .. .. .. ... ... ....... .......... ............ ........ .... ...... ..... .... . ... .. .................. ................. . .......................................................................................... ...... ........... . ... ... ... .... .... .... ................................... ........... .. ... . ... ... ... ... ... ............. ........... ........ .. .... ... ... ... ... ...................................... ...................... .............. .. .. . .................................. ...................................... . .. . ... . . ........... ............... ........................................... .. . .. ... . .. .. .. .. .. ... .... ..... ................................................. .. ....... . .... ... .. ......... . .. ... ... ..... ............... .... ... .. .. .. . ........... ... . ......................... ♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣ ♣ ♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣ ♣ ♣♣♣♣♣♣♣♣♣♣♣♣♣♣ ♣♣♣♣♣♣ ♣ .................................................................... . . ... ... ... .. .. ... ....... .. .................................................................. . .. ... ... ... .. .. .. .. .. ........ ..................................................................................................... .... ..... ..... ..... ..... ..... ..... .... ... ... .... .. ... .. .................. .. .. ... ....... .. . ............................ .. .. .............................................................. ♣ ♣♣♣♣♣♣♣♣ ♣ ♣ ♣ ♣♣♣♣♣♣♣♣♣ ♣ ♣ ♣ ♣ ♣♣♣♣♣♣♣♣♣♣♣♣♣ ♣ ♣ ♣ ♣ ♣ ♣ ♣ ♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣ ♣ ♣ ♣ ♣♣♣♣ ♣ ♣ ♣ ♣♣ ♣♣♣♣ ♣♣♣ ♣♣ ♣♣♣♣ ♣♣ ♣ ♣ ♣ ♣ ♣♣ ♣ ♣♣♣♣♣♣♣♣♣♣♣ ♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣ ♣ s s s s s s s s s s ♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣ ♣ ♣ ♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣ ♣ ♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣ ♣ ♣ ♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣ ♣ ♣ ♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣ ♣ ♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣ ♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣ ♣♣♣♣♣ ♣ ♣♣♣♣♣♣♣♣♣ ♣ ♣ ♣ ♣♣♣♣♣♣♣♣♣ ♣ ♣ ♣ ♣ ♣♣♣♣♣♣♣♣♣♣♣♣♣ ♣ ♣ ♣ ♣ ♣ ♣ ♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣ ♣ s ♣ ♣ ♣♣ ♣♣ ♣ ♣♣♣♣♣ ♣♣♣♣ ♣♣ ♣♣ ♣ ♣ ♣♣ ♣♣♣ ♣ ♣ ♣♣ ♣ ♣♣♣♣♣♣♣♣♣♣♣ ♣♣♣♣♣♣♣♣♣♣♣♣♣♣ ♣ s s s s s s s s s Figure 8: A map and corresponding planar graph In 1878 Sylvester referred to a linkage as a graph and it is this terminology that became accepted. Later it became commonplace to refer to the points and lines of a linkage as the vertices and edges of the graph (with “vertex” being the singular of “vertices”). Since the graphs constructed from maps in this manner (referred to as the dual graph of the map) can themselves be drawn in the plane without two edges (line segments) intersecting, these graphs were called planar graphs. A planar graph that is actually drawn in the plane without any of its edges intersecting is called a plane graph. In terms of graphs, the Four Color Conjecture could then be restated. The Four Color Conjecture The vertices of every planar graph can be colored with four or fewer colors in such a way that every two vertices joined by an edge are colored differently. Indeed, the vast majority of this book will be devoted to coloring graphs (not coloring maps) and, in fact, to coloring graphs in general, not only planar graphs
12CHAPTER 0.THE ORIGIN OF GRAPH COLORINGSThe colouring of abstract graphs is a generalization of the colouring ofmaps, and the study of the colouring of abstract graphs ..- opens a newchapter in the combinatorial part of mathematics.Gabriel Andrew Dirac (1951)For the present, however, we continue our discussion in terms of coloring theregionsofmapsKempe's proof of the theorem, which had become known as the Four ColorTheorem, was accepted both within the United States and England.Arthur Cayleyhad acceptedKeargument as a valid proof. This led to Kempe being electedasaFellowof theRoval Society in 1881The Four Color Theorem The regions of every map can be colored with four orfewer colors sothat everytwo adjacentreqions are colored differentlyy individuals who had become interested in the Four ColonongthProblem was Charles Lutwidge Dodgson (1832-1898), an Englishmannwithakeerinterest in mathematics and puzzles. Dodgson was better known, however, underhis pen-name Lewis Carroll and for his well-known books Alice's Adventures inWonderland and Through the Looking-Glass and What Alice Found There.Another well-known individual with mathematical interests, but whose primaryoccupation was not that of a mathematician, was Frederick Temple (1821-1902),Bishop of London and who would later become the Archbishop of Canterbury.LikeDodgson and others, Temple had a fondness for puzzleTempleshowedthat itas impossibleto have five mutually neighboring regions in any mapandfromthisconcluded that no map required five colors.Although Temple was correct aboutthe non-existence of five mutually neighboring regions in a map, his conclusion thatthis provided aproof of the Four Color Conjecturewas incorrectThere was historical precedence about thenon-existenceof five mutually adacent regions in any map. In 1840 the famous German mathematician AugustMobius (1790-1868)reportedly stated thefollog problem,which was proposedto him by the philologist Benjamin Weiske (1748-1809).Problem of Five PrincesThere was once a king with five sons. In his will, he stated that after hisdeath his kingdom should be divided into five regions in such a way thateach region should have a common boundary with the other four: Canthe terms of the will be satisfied?As we noted, the conditions of the king's will cannot be met. This problemillustrates Mobius' interest in topologubject of which Mobius was one of theearly pioneers. In a memoir written by Mobius and only discovered after his death,he discussed properties of one-sided surfaces, which became known as Mobius strips(even though it was determined that Johann Listing (1808-1882) had discoveredthese earlier)
12 CHAPTER 0. THE ORIGIN OF GRAPH COLORINGS The colouring of abstract graphs is a generalization of the colouring of maps, and the study of the colouring of abstract graphs . . . opens a new chapter in the combinatorial part of mathematics. Gabriel Andrew Dirac (1951) For the present, however, we continue our discussion in terms of coloring the regions of maps. Kempe’s proof of the theorem, which had become known as the Four Color Theorem, was accepted both within the United States and England. Arthur Cayley had accepted Kempe’s argument as a valid proof. This led to Kempe being elected as a Fellow of the Royal Society in 1881. The Four Color Theorem The regions of every map can be colored with four or fewer colors so that every two adjacent regions are colored differently. Among the many individuals who had become interested in the Four Color Problem was Charles Lutwidge Dodgson (1832–1898), an Englishman with a keen interest in mathematics and puzzles. Dodgson was better known, however, under his pen-name Lewis Carroll and for his well-known books Alice’s Adventures in Wonderland and Through the Looking-Glass and What Alice Found There. Another well-known individual with mathematical interests, but whose primary occupation was not that of a mathematician, was Frederick Temple (1821–1902), Bishop of London and who would later become the Archbishop of Canterbury. Like Dodgson and others, Temple had a fondness for puzzles. Temple showed that it was impossible to have five mutually neighboring regions in any map and from this concluded that no map required five colors. Although Temple was correct about the non-existence of five mutually neighboring regions in a map, his conclusion that this provided a proof of the Four Color Conjecture was incorrect. There was historical precedence about the non-existence of five mutually adjacent regions in any map. In 1840 the famous German mathematician August M¨obius (1790–1868) reportedly stated the following problem, which was proposed to him by the philologist Benjamin Weiske (1748–1809). Problem of Five Princes There was once a king with five sons. In his will, he stated that after his death his kingdom should be divided into five regions in such a way that each region should have a common boundary with the other four. Can the terms of the will be satisfied? As we noted, the conditions of the king’s will cannot be met. This problem illustrates M¨obius’ interest in topology, a subject of which M¨obius was one of the early pioneers. In a memoir written by M¨obius and only discovered after his death, he discussed properties of one-sided surfaces, which became known as M¨obius strips (even though it was determined that Johann Listing (1808–1882) had discovered these earlier)
1n1885theGernman geometer Richard Baltzer (1818-1887) also lectured on thenon-existence of five mutually adjacent regions. In the published version of hislecture, t was incorrectly stated that the Four Color Theorem followed from this.This error was repeated by other writers until the famous geometer Harold ScottMacDonaldCoxeter (1907-2003)correctedthematterin1959Mistakes concerning the Four Color Problem were not limited to mathematicalPrior to establishing Francis Guthrie as the true and sole originatorerrorshoweverof the Four Color Problem,it was often stated in print that cartographers wereawarethattheregions ofeverymap could becolored withfour or lessscolorssothatadjacent recoloreddifferently.Thewell-knoymathematical historianKenneth O.May (1915-1977)investigated this claim and found no justification toit.Hecoucteda study ofatlases in theLibraryof Congressand found noevidenceofattemptstmzethenumber of colors used inmaps.Mostmaps usedmorethanand even when four colors were used, ooftenlesscolorscouldhaveamention ofa"four colortheoremdAnother mathematician of note around 1880 was Peter Guthrie Tait (1831)1901). In addition to being a scholar, he was a golf enthusiast. His son FrederickGuthrie Tait was a champion golfer and considered a national hero in Scotland.The first golf biography ever written was about Frederick Tait. Indeed, the FreddieTait Golf Week is held every year in Kimberley, South Africa to comemorate hislife as a golfer and soldier. He was killed during the Anglo-Boer War of 1899-1902Peter Guthrie Tait had heard of the Four Color Conjecture through ArthulCayley and wasaware of Kempe's solution.HefeltthatKempe's solutionoftheFourColor Probloverly long and gave several shorter solutions of the problemall of which turnedout tobe incorrect.Despite this, one of his attempted proofsg and useful idea. A type of map that is often encountered isnntainedanira cubic map, in which there are exactly three boundary lines at each meeting pointInfact,everymapMthathasnoregioncompletelysuroundedbyanotherregioncan be converted into a cubic map M' by drawing a circle about each meeting pointin M'and creatingmeeting points and one new region (see Figure 9). If themap M'can be colored with four colors,then so can MX--○in MinMFigure 9: Converting a map into a cubic mapTait's idea was to consider coloring the boundary lines of cubic maps. In fact.he stated as a lemma that:
13 In 1885 the German geometer Richard Baltzer (1818–1887) also lectured on the non-existence of five mutually adjacent regions. In the published version of his lecture, it was incorrectly stated that the Four Color Theorem followed from this. This error was repeated by other writers until the famous geometer Harold Scott MacDonald Coxeter (1907–2003) corrected the matter in 1959. Mistakes concerning the Four Color Problem were not limited to mathematical errors however. Prior to establishing Francis Guthrie as the true and sole originator of the Four Color Problem, it was often stated in print that cartographers were aware that the regions of every map could be colored with four or less colors so that adjacent regions are colored differently. The well-known mathematical historian Kenneth O. May (1915–1977) investigated this claim and found no justification to it. He conducted a study of atlases in the Library of Congress and found no evidence of attempts to minimize the number of colors used in maps. Most maps used more than four colors and even when four colors were used, often less colors could have been used. There was never a mention of a “four color theorem”. Another mathematician of note around 1880 was Peter Guthrie Tait (1831– 1901). In addition to being a scholar, he was a golf enthusiast. His son Frederick Guthrie Tait was a champion golfer and considered a national hero in Scotland. The first golf biography ever written was about Frederick Tait. Indeed, the Freddie Tait Golf Week is held every year in Kimberley, South Africa to commemorate his life as a golfer and soldier. He was killed during the Anglo-Boer War of 1899–1902. Peter Guthrie Tait had heard of the Four Color Conjecture through Arthur Cayley and was aware of Kempe’s solution. He felt that Kempe’s solution of the Four Color Problem was overly long and gave several shorter solutions of the problem, all of which turned out to be incorrect. Despite this, one of his attempted proofs contained an interesting and useful idea. A type of map that is often encountered is a cubic map, in which there are exactly three boundary lines at each meeting point. In fact, every map M that has no region completely surrounded by another region can be converted into a cubic map M′ by drawing a circle about each meeting point in M′ and creating new meeting points and one new region (see Figure 9). If the map M′ can be colored with four colors, then so can M. . .. ... .... ...... ........ ............... .............. ...... ........ ..... .... ... .... ................................................................................. . . . .. ... .... ...... ........ ...................... .... ............... ...... .... ... .. .. ................................................................................. . ...................................... .. . . . . . . . . . . . . . . . . . . . . . ........... .. . .. .......... ......... . . . . . . . . . . . . . . . . . . . . . . ....................................... ......................................................................................................................................... ................................................................... ............ .. .. .. .. .. .. .. .. .. ......... . . . .. ... .......... ........ .......................... ............................. ...................................................................... in M in M′ Figure 9: Converting a map into a cubic map Tait’s idea was to consider coloring the boundary lines of cubic maps. In fact, he stated as a lemma that:
14CHAPTER 0.THE ORIGIN OF GRAPH COLORINGSThe boundary lines of every cubic map can alaways be colored with threecolors so that the three lines at each meeting point are colored differently.Tait also ntioned that this lemma could be easilyproved and showed howthelemmacouldbeusedtoprovetheFourColorTheoremAlthoughTait wascorrectthat this lenma could be used to to prove the Four Color Theorem, he was incorrectwhen he said that the lemma could be easily proved. Indeed, as it turned out, thislemma isequivalent to theFour ColorTheorem and, of course, isequally dfficulttoprove.(We willdiscuss Tait'scoloring oftheboundarylinesofcubicmapsinChapter 10.The next important figure in the history of the Four Color Problem was PercyJohn Heawood (1861-1955), who spent the period 1887-1939 as a lecturer, professorand vice-chancellor at Durham College in England. When Heawood was a studentat Oxford University in 1880, one of his teachers was Professor Henry Smith whospoke often of the Four Color Problem.Heawood read Kempe's paper and it washewhodiscovered theseriouserror intheproof.In1889Heawood wroteapaperof his own, published in 1890, in which he presented the map shown in Figure 10.Figure 10:Heawood'sxampletoKempe'sprooIntheHeawood map,twoof thefiveneighboring regions surroundingtheuncolored region R are colored red; while for each of the colors blue, yellow,and greenthere is exactly one neighboring region of R with that color.According to Kempe'sargument. since blue is the color of the region that shares a boundary with R aswell as with the two neighboring regions of R colored red. we are concerned withwhether this map contains a blue-yellow Kempe chain between two neighboring rgions of R as well as a blue-green Kempe chain between two neighboring regions of
14 CHAPTER 0. THE ORIGIN OF GRAPH COLORINGS The boundary lines of every cubic map can always be colored with three colors so that the three lines at each meeting point are colored differently. Tait also mentioned that this lemma could be easily proved and showed how the lemma could be used to prove the Four Color Theorem. Although Tait was correct that this lemma could be used to to prove the Four Color Theorem, he was incorrect when he said that the lemma could be easily proved. Indeed, as it turned out, this lemma is equivalent to the Four Color Theorem and, of course, is equally difficult to prove. (We will discuss Tait’s coloring of the boundary lines of cubic maps in Chapter 10.) The next important figure in the history of the Four Color Problem was Percy John Heawood (1861–1955), who spent the period 1887–1939 as a lecturer, professor, and vice-chancellor at Durham College in England. When Heawood was a student at Oxford University in 1880, one of his teachers was Professor Henry Smith who spoke often of the Four Color Problem. Heawood read Kempe’s paper and it was he who discovered the serious error in the proof. In 1889 Heawood wrote a paper of his own, published in 1890, in which he presented the map shown in Figure 10. r g b y y b . ................ .. .. .... ...................... ....................... ............. ................................................. ................................................ ...................................................... . ......... .. ................ .. .... . ... .. .. .. ....... .. . .. .. .... .. .. .. .. .. .. .. .. .. ... .. . . ................. ............. ...... .. ... .. .. .. .. .. ... .. ...... .... ... .. ..... ........ ....................... .. .. ... .... ... .. .. .. ........... ....... .... .... .. ... . ..... ..................... .................... . ... ... ... .. . . .. ... . ... .. ..... .. .. .. ... ... ........... ......... .. . ... . .. ... . .... .......... ... ................. ... .... .... ..... ..... ..... ..... ......... ......... ........ ................. ....... .... ..... ... .... ...... .......... ................... ... ... ... ... .. ................ ......................... ............ .............. .. ... ... ... .... . ...... .. . .. .. ... .. .. .. .. ... ... . ....... .. . .. ... .. ... .. ... .. ........................ ...................................................... . .... ... .. ... .. . ..... .... . .... . r R g y g b y g b r r g y b r g y r b ............... . ................. .. .. ....... . ... .. ... .. .. ....... ... .. ... ......... ... .. .. .. . .. ... .. ... ................. ...... ...... ..... ... ............................................................................................. ....... .... ... .......... ................... ...... . ... ............................ ......................... ............................................... .. .. .. ... ... .. . . . .. ..... ... ...... ... ... .. . ............ ............................ .......................... . . ... . ................... ...................................... .. .. ..... . ... ................ .... ... ... .. ............ ........ . ................. . ....................................................................... . ... ... ... ... ............... ..... .... ... ... .. .................. ... .................... . ..................... ........................ .... ... . . .. ..... .. .......... ..... .. ...... ......................... .. .. . .... ......... ..... ............ .... ..... ..... ... ....... .......... ... ..... ....................................................... .. ... ... .... .. .. .. .. .. .. .. . ... .. .. . . .................................... .......................................................... .. ............ ..... .... ... .. ... .. .. ........................... . ... .................................. . ... ... .. ... . ... ............................. ....................................... ............... . .. ... ... ..... ..... . . .. .. ............................ ... ............................... ......... . .... ...................... .. ... .... ... .. ......... .. ........ .................. .. ....... . .. ........ .. .. ..... .. ......... . .. . ... .... ... ... .. .... ... . ... .. ............................. .............................. .. ............. .................. ......... . ......... . ................ .... . .... .. ... ... ..... . . ............................................. Figure 10: Heawood’s counterexample to Kempe’s proof In the Heawood map, two of the five neighboring regions surrounding the uncolored region R are colored red; while for each of the colors blue, yellow, and green, there is exactly one neighboring region of R with that color. According to Kempe’s argument, since blue is the color of the region that shares a boundary with R as well as with the two neighboring regions of R colored red, we are concerned with whether this map contains a blue-yellow Kempe chain between two neighboring regions of R as well as a blue-green Kempe chain between two neighboring regions of