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 in15 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 con￾tain 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 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’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