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 of14 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 uncol￾ored 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 re￾gions of R as well as a blue-green Kempe chain between two neighboring regions of