gions.Thisincludedlookingregforchainof regions whoses alternatebetweentwo colorsand theninterchangingthesecolors, if appropriate, to arrive at a coloring of the regions of M (minus R) withfoulhat the neighboring regions of R used at most three of these colorsTcolorssoand thereby leaving a color available for R. In fact, these chains of regions becameknown as Kempe chains, foritwas Kempewho originated this ideawas one case, however, that still needed to be resolved, namely the casen the map was surrounded by four or fewer neighboring regions.whereno regiorAs we noted, the map must then contain some region R surrounded by exactly fiveAt least three of the four colors must be used to color the fiveneighboring regions.neighboring regions of R. If only three colors are used to color these five regionsthen a color is available for R. Hence we are left with the single situation in whichall four colors are used to color thefiveneighboringregions surroundingR (seeFigure 5),where once agaib,g,y indicatethe colorsred,blue,green,yellowRFigure5:Thefinal case in Kempe'ssolution of theFour ColorProblemLet's seehow Kempe handled this final case.Among theregions adiacent to Ronlythe region R is colored yellow. Consider all theregions of the map M thatare colored either vellow or red and that. beginning at Ri. can be reached by analternating seguence of neighboring vellow and red regions.that is.by a vellow-redKempe chain. If the repion Ra (which is the neighboring region of R colored red)cannot be reached by a vellow-red Kempe chain.then the colors vellow and red canbe interchanged for all regions in M that can be reached by a yellow-red Kempechain beginning at Ri This results in a coloring of all regions in M (except R)eighborirecoloreddifferentlyand suchthateachneighboriWEn0region of Risolored red. blue.orgreen.Wecanthen colorRvellowtoarrriveatre map M. From this, we may asthat the region Rg can20or1moffne11be reached by a yellow-red Kempe chain beginning at Ri. (See Figure 6.Let's now look at the region Rs, which is colored green. We consider all regionsof M colored green or red and that, beginning at Rs, can be reached by a green-redKempe chain. If the region Rg cannot be reached by a green-red Kempe chain thatbegins at Rs, then the colors green and red can be interchanged for all regions in M9 surrounded by four or fewer neighboring regions. This included looking for chains of regions whose colors alternate between two colors and then interchanging these colors, if appropriate, to arrive at a coloring of the regions of M (minus R) with four colors so that the neighboring regions of R used at most three of these colors and thereby leaving a color available for R. In fact, these chains of regions became known as Kempe chains, for it was Kempe who originated this idea. There was one case, however, that still needed to be resolved, namely the case where no region in the map was surrounded by four or fewer neighboring regions. As we noted, the map must then contain some region R surrounded by exactly five neighboring regions. At least three of the four colors must be used to color the five neighboring regions of R. If only three colors are used to color these five regions, then a color is available for R. Hence we are left with the single situation in which all four colors are used to color the five neighboring regions surrounding R (see Figure 5), where once again r, b, g, y indicate the colors red, blue, green, yellow. . ... ... ... ... . ..................................................................... ........ . . .. .. ............... ....... . . . . . . . . ............... .. ... ... ... .. .. ... ... .. ... .. ... ... ... . ................. . . . ..................................................................................... ................................. . . .. .. .. ... .... ........... .... .. .. . .... ..... ...... ..... ..................... .... ....... ........ .............. ........ ..... ... ... ... .... ..... .. .......... .. ... . . .. .. .. ... ... ....... ...... .......................... ............... . ... ..... ...... ..... . ........... ..... .. ................................. . . . ................................. . ..... ... .. ..... ... ... ....... .... ... ... . ... .. .. ... .................................................... ....................................................... .................................................... .......................................... .............. ........ ... .. .. ..... .. ............................................. ... ... .. ... .... ... ... ..... ........... ..... .... ... .. . .. ... ...... .......... ........ ... ........... . .......................................................... ............................................. ......... ......................... .. ... ... ... .. .. ... ... ..... .. .. ... .. ... .. .. . .... . . .. . ... . ............................ ...................... R g y b r b R4 R2 R5 R3 R1 Figure 5: The final case in Kempe’s solution of the Four Color Problem Let’s see how Kempe handled this final case. Among the regions adjacent to R, only the region R1 is colored yellow. Consider all the regions of the map M that are colored either yellow or red and that, beginning at R1, can be reached by an alternating sequence of neighboring yellow and red regions, that is, by a yellow-red Kempe chain. If the region R3 (which is the neighboring region of R colored red) cannot be reached by a yellow-red Kempe chain, then the colors yellow and red can be interchanged for all regions in M that can be reached by a yellow-red Kempe chain beginning at R1. This results in a coloring of all regions in M (except R) in which neighboring regions are colored differently and such that each neighboring region of R is colored red, blue, or green. We can then color R yellow to arrive at a 4-coloring of the entire map M. From this, we may assume that the region R3 can be reached by a yellow-red Kempe chain beginning at R1. (See Figure 6.) Let’s now look at the region R5, which is colored green. We consider all regions of M colored green or red and that, beginning at R5, can be reached by a green-red Kempe chain. If the region R3 cannot be reached by a green-red Kempe chain that begins at R5, then the colors green and red can be interchanged for all regions in M