implying that M could be colored with four colors after all, thereby producing acontradictionCertainly,fthmapMonainsonsurounddbyweththree regions, a contradiction can be obtained in the same manner.8-人-8er0240(a) in M(c) in M(b) in MFigure 2: A region surrounded by three regions in a mapSuppose, however, that the map M contained no region surrounded by three orfewer regions but did contain a region R surrounded by four regions, say Ri, R2.R3,R4, as shown in Figure 3(a). If, once again, we shrink the region R to a point,producinga map M'with onelessregion,then weknow that M'can be coloredwith four colors.If two or three colors areused to color Ri,R2,R3,R4,then we canreturn to M and there is a color available for R. However, this technique does notwork if the regions Ri,R2, R3, Ry are colored with four distinct colors, as shownin Figure 3(b).Hredblueyellowgreen(b) in M'(a) in MFigure3:A region surrounded byfour regions in a maWhat we can do in this case,however.is todeterminewhether themap M' hasa chain of regions,beginning at R, and ending at R3,all of which are colored redor green. If no such chain exists, then the two colors of every red-green chain ofregions beginning at Ri can be interchanged. We can then return to the map M,where the color red is now available for R. That is, the map M can be colored withfourcolors, producing a contradictionBut what ifared-geen chain ofregionsbeginning at Ri and ending at Rs exists? (See Figure 4, where r,b, g,y denote thecolors red, blue, green, yellow.) Then interchanging the colors red and green ofersno benefit to us. However, in this case, there can be no blue-yellow chain of regions,beginning at R2 and ending at R4-Then the colors of every blue-yellow chain of7 implying that M could be colored with four colors after all, thereby producing a contradiction. Certainly, if the map M contains a region surrounded by fewer than three regions, a contradiction can be obtained in the same manner. . .. ... ...... .......... .......... ......... ...... .... ... ................................................... . .. .... ..... ............... ....... ........... .... .. .. ................................................... . . . . . . . . . .. .............. .... . . . . . . . . . . . . . . . . . .. .................. .......... . . .. . .. ......... ........ .......... . . .. . .. ......... ........ ..................... R (a) (c) blue green red R3 green (b) in M′ in M in M R2 R1 yellow blue yellow Figure 2: A region surrounded by three regions in a map Suppose, however, that the map M contained no region surrounded by three or fewer regions but did contain a region R surrounded by four regions, say R1, R2, R3, R4, as shown in Figure 3(a). If, once again, we shrink the region R to a point, producing a map M′ with one less region, then we know that M′ can be colored with four colors. If two or three colors are used to color R1, R2, R3, R4, then we can return to M and there is a color available for R. However, this technique does not work if the regions R1, R2, R3, R4 are colored with four distinct colors, as shown in Figure 3(b). . .. .... ..... ............... ........ .......... .... .. .. ................................................... . .......... . .. ... .......... ......... ................................................................................................................................................................................. R R3 R1 green red R4 blue yellow R2 (a) in M (b) in M′ Figure 3: A region surrounded by four regions in a map What we can do in this case, however, is to determine whether the map M′ has a chain of regions, beginning at R1 and ending at R3, all of which are colored red or green. If no such chain exists, then the two colors of every red-green chain of regions beginning at R1 can be interchanged. We can then return to the map M, where the color red is now available for R. That is, the map M can be colored with four colors, producing a contradiction. But what if a red-green chain of regions beginning at R1 and ending at R3 exists? (See Figure 4, where r, b, g, y denote the colors red, blue, green, yellow.) Then interchanging the colors red and green offers no benefit to us. However, in this case, there can be no blue-yellow chain of regions, beginning at R2 and ending at R4. Then the colors of every blue-yellow chain of