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 maps16 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