11blue and green for all regions in M that can be reached by a blue-green Kempechain beginning at R2. Once these two color interchanges have been performedeach of the five neighboring regions of R is colored red, yllow, or green. Then Rcan be colored blue and a 4-coloring of the map M has been obtained, completingthe proofAs it turned out, the proof given by Kempe contained a fatal flaw,but onethat would go unnoticed for a decade. Despite the fact that Kempe's attemptedproof of theFour ColorProblem was erroneous,he madeanumber of interestingobservations in his article. He noticed that if a piece of tracing paper was placedover a map and a point was marked on the tracing paper over each region of thewo points were joined by a line segment whenever the correspondingmaboundary, then a diagram of a "linkage""was produced.regionshadnonaomFurthermore, the problem of determining whether the regions of the map can becolored with focolors so that neighboring regionss are colored differently is theiningwhetherthepoinsinthelinkagecanbecoloredwithproblenfour colors so that every two points joined by a line segment are colored differently(See Figure 8.)Figure 8: A map and corresponding planar graplIn 1878 Sylvester referred to a linkage as a graph and it is this terminology thatbecame accepted. Later it became commonplace to refer to the points and lines ofa linkage as the vertices and edges of the graph (with "vertex" being the singularof "vertices"). Since the graphs constructed from maps in this manner (referred toas the dual graph of the map) can themselves be drawn in the plane without twoedges(linesegments)intersecting,thesegraphswere calledplanar graphs.Aplanargraph that is actually drawn in the plane without any of its edges intersecting iscalled a plane graph. In terms of graphs, the Four Color Conjecture could then berestatedThe Four Color Conjecture The vertices of every planar graph can be coloredwith four or fewer colors in such a way that every two vertices joined by an edgeare colored differently.Indeed, the vast majority of this book will be devoted to coloring graphs (notcoloring maps)and, in fact, to coloring graphs in general, not only planar graphs11 blue and green for all regions in M that can be reached by a blue-green Kempe chain beginning at R2. Once these two color interchanges have been performed, each of the five neighboring regions of R is colored red, yellow, or green. Then R can be colored blue and a 4-coloring of the map M has been obtained, completing the proof. As it turned out, the proof given by Kempe contained a fatal flaw, but one that would go unnoticed for a decade. Despite the fact that Kempe’s attempted proof of the Four Color Problem was erroneous, he made a number of interesting observations in his article. He noticed that if a piece of tracing paper was placed over a map and a point was marked on the tracing paper over each region of the map and two points were joined by a line segment whenever the corresponding regions had a common boundary, then a diagram of a “linkage” was produced. Furthermore, the problem of determining whether the regions of the map can be colored with four colors so that neighboring regions are colored differently is the same problem as determining whether the points in the linkage can be colored with four colors so that every two points joined by a line segment are colored differently. (See Figure 8.) ....................................................... ... . .. .. .. ... ... ....... .......... ............ ........ .... ...... ..... .... . ... .. ................ .. ................. . ........................................................................................ ...... ........... . ... ... ... .... .... .... .................................. ........... .. ... . ... ... .. ... ... ............. ........... ........ .. .... ... ... ... ... ...................................... ...................... .............. .. .. . .................................. ...................................... . .. . ... . . ........... ............... ........................................... .. . .. ... . .. .. .. .. ... ... .... ..... ................................................. .. ....... . ..... ... .. ......... . .. ... ... ..... ............... .... ... .. .. .. . ........... ... . ......................... .................................................................... . . ... ... ... .. .. ... ....... .. ................................................................. .... ..... ..... ..... ..... ..... ..... .... ... ... .... .. ... .. .............. . ... .. .. ... ....... .. . ............................ .. .. .............................................................. . .. ... ... ... .. .. .. .. .. ........ ..................................................................................................... ....................................................... ... . .. .. .. ... ... ....... .......... ............ ........ .... ...... ..... .... . ... .. .................. ................. . .......................................................................................... ...... ........... . ... ... ... .... .... .... ................................... ........... .. ... . ... ... ... ... ... ............. ........... ........ .. .... ... ... ... ... ...................................... ...................... .............. .. .. . .................................. ...................................... . .. . ... . . ........... ............... ........................................... .. . .. ... . .. .. .. .. .. ... .... ..... ................................................. .. ....... . .... ... .. ......... . .. ... ... ..... ............... .... ... .. .. .. . ........... ... . ......................... ♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣ ♣ ♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣ ♣ ♣♣♣♣♣♣♣♣♣♣♣♣♣♣ ♣♣♣♣♣♣ ♣ .................................................................... . . ... ... ... .. .. ... ....... .. .................................................................. . .. ... ... ... .. .. .. .. .. ........ ..................................................................................................... .... ..... ..... ..... ..... ..... ..... .... ... ... .... .. ... .. .................. .. .. ... ....... .. . ............................ .. .. .............................................................. ♣ ♣♣♣♣♣♣♣♣ ♣ ♣ ♣ ♣♣♣♣♣♣♣♣♣ ♣ ♣ ♣ ♣ ♣♣♣♣♣♣♣♣♣♣♣♣♣ ♣ ♣ ♣ ♣ ♣ ♣ ♣ ♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣ ♣ ♣ ♣ ♣♣♣♣ ♣ ♣ ♣ ♣♣ ♣♣♣♣ ♣♣♣ ♣♣ ♣♣♣♣ ♣♣ ♣ ♣ ♣ ♣ ♣♣ ♣ ♣♣♣♣♣♣♣♣♣♣♣ ♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣ ♣ s s s s s s s s s s ♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣ ♣ ♣ ♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣ ♣ ♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣ ♣ ♣ ♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣ ♣ ♣ ♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣ ♣ ♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣ ♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣ ♣♣♣♣♣ ♣ ♣♣♣♣♣♣♣♣♣ ♣ ♣ ♣ ♣♣♣♣♣♣♣♣♣ ♣ ♣ ♣ ♣ ♣♣♣♣♣♣♣♣♣♣♣♣♣ ♣ ♣ ♣ ♣ ♣ ♣ ♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣♣ ♣ s ♣ ♣ ♣♣ ♣♣ ♣ ♣♣♣♣♣ ♣♣♣♣ ♣♣ ♣♣ ♣ ♣ ♣♣ ♣♣♣ ♣ ♣ ♣♣ ♣ ♣♣♣♣♣♣♣♣♣♣♣ ♣♣♣♣♣♣♣♣♣♣♣♣♣♣ ♣ s s s s s s s s s Figure 8: A map and corresponding planar graph In 1878 Sylvester referred to a linkage as a graph and it is this terminology that became accepted. Later it became commonplace to refer to the points and lines of a linkage as the vertices and edges of the graph (with “vertex” being the singular of “vertices”). Since the graphs constructed from maps in this manner (referred to as the dual graph of the map) can themselves be drawn in the plane without two edges (line segments) intersecting, these graphs were called planar graphs. A planar graph that is actually drawn in the plane without any of its edges intersecting is called a plane graph. In terms of graphs, the Four Color Conjecture could then be restated. The Four Color Conjecture The vertices of every planar graph can be colored with four or fewer colors in such a way that every two vertices joined by an edge are colored differently. Indeed, the vast majority of this book will be devoted to coloring graphs (not coloring maps) and, in fact, to coloring graphs in general, not only planar graphs