17that can be drawn on the surface of a sphere.There are considerably more complexsurfaces on which maps can be drawn, however. In particular, Heawood proved thattheregions ofevervmap drawn on the surfaceof atorus canbe colored with seven orfewer colors and that there is, in fact.a map on the torus that requires seven colors(see Chapter 8).More generally, Heawood showed that the regions of every mapdrawn on a pretzel-shaped surface consisting of a sphere with k holes (k > O) canbe colored with7+V+48kcolors. In addition, he stated that such maps requiringthis number of colors exist.He never proved this latter statement, however. In fact,it would take another 78 years to verify this statement (see Chapter 8).Thus the origin of a curious problem by the young scholar Francis Guthrie wasfollowed over a quarter of a century later bywhat was thought to be a solutiontotheproblembyAlfredBrayKempe.However,weweretolearnfromPercyJohn Heawood a decade later that the solutiowas erroneous,whichreturned theproblemto its priorstatus.Well notquite-asthese eventsproved tobe steppingstones along the path to chromatic graph theory.Is it five?Is it four?Heawood rephrased the query.Sending us back to before,But moving forward a theory.At the beginning of the 20th century,the Four Color Problem was still unsolved.Although possibly seen initially as a rather frivolous problem, not worthy of a seriousmathematician's attention, it would become clear that the Four Color Problem wasa very challenging mathematics problem.Many mathematicians, using a variety ofapproaches,would attackthisproblemduringthe1900s.Asnoted,itwasknownthat if the Four Color Conjecture could be verified for cubic maps, then the FourColor Conjecture would be true for all maps. Furthermore, every cubic map mustcontain a region surrounded by two,three,four,or five neighboring regions.Thesefour kinds of configurations (arrangements of regions)were called unavoidable be-cause every cubic map had to contain at least one of them. Thus the arrangementsof regions shown in Figure14 makeup an unavoidable set of configurations.Figure14:An unavoidable set of configurations in a cubicmapA region surrounded by k neighboring regions is called a k-gon. It is possibleto show that any map that contains no k-gon where k < 5 must contain at least17 that can be drawn on the surface of a sphere. There are considerably more complex surfaces on which maps can be drawn, however. In particular, Heawood proved that the regions of every map drawn on the surface of a torus can be colored with seven or fewer colors and that there is, in fact, a map on the torus that requires seven colors (see Chapter 8). More generally, Heawood showed that the regions of every map drawn on a pretzel-shaped surface consisting of a sphere with k holes (k > 0) can be colored with j 7+√ 1+48k 2 k colors. In addition, he stated that such maps requiring this number of colors exist. He never proved this latter statement, however. In fact, it would take another 78 years to verify this statement (see Chapter 8). Thus the origin of a curious problem by the young scholar Francis Guthrie was followed over a quarter of a century later by what was thought to be a solution to the problem by Alfred Bray Kempe. However, we were to learn from Percy John Heawood a decade later that the solution was erroneous, which returned the problem to its prior status. Well not quite – as these events proved to be stepping stones along the path to chromatic graph theory. Is it five? Is it four? Heawood rephrased the query. Sending us back to before, But moving forward a theory. At the beginning of the 20th century, the Four Color Problem was still unsolved. Although possibly seen initially as a rather frivolous problem, not worthy of a serious mathematician’s attention, it would become clear that the Four Color Problem was a very challenging mathematics problem. Many mathematicians, using a variety of approaches, would attack this problem during the 1900s. As noted, it was known that if the Four Color Conjecture could be verified for cubic maps, then the Four Color Conjecture would be true for all maps. Furthermore, every cubic map must contain a region surrounded by two, three, four, or five neighboring regions. These four kinds of configurations (arrangements of regions) were called unavoidable be￾cause every cubic map had to contain at least one of them. Thus the arrangements of regions shown in Figure 14 make up an unavoidable set of configurations. .................................... ...................................... . ............ . . .............................................. ......................................... ..... .. .......... . . . . . . . . . . . . . . . . . . . ... ... .... ..... ......... ... . ...... ...... .... ....... .... ....... ... .... .. .. . . . . . . . . . ...... .......... .......... .......... .......... .......... ......... ...... . . . . . . . . .. .. . .... .... ........ .. .. ...... .... ...... ........ .... ...... .... ... ... .. . . . . . . . ...... ......... .......... .......... .......... .......... .......... ...... . . . . . . . . . ... .. . .... ..... ........ .. .. ...... .... ...... ........ .... ...... .... .... ... .. . . . . . . . . . ...... .......... .......... .......... .......... .......... ......... ...... .. . . . . .. ...... ............. ... . ........................ . . . . .. .. . .... .... ........ ... .. ...... ..... ..... ....... .... ...... ... ... ... .. . . . . . . . ...... ......... .......... .......... .......... .......... .......... ...... . . . . . .. ............................. ..................................... Figure 14: An unavoidable set of configurations in a cubic map A region surrounded by k neighboring regions is called a k-gon. It is possible to show that any map that contains no k-gon where k < 5 must contain at least