CHAPTER 0.THE ORIGIN OFGRAPH COLORINGSenehGuBrazBoliviaaraguaPacific OceanAtlanticOcea Falkland IslancFigure I: Map of South AmericaMany of the concepts, theorems, and problems of Graph Theory lie in the shadows of the Four Color Problem. Indeed ...Graph Theory is an area of mathematics whose past is aluays presentSince the maps we consider can be real or imagined, we can think of maps beingdivided into more general regions, rather than countries, states, provinces, or someother geographic entities.So just how did the Four Color Problem begin? It turns out that this questionhas arather well-documented answer.On 23October 1852,a student,namelyFred-erick Guthrie (1833-1886).at University College London visited his mathematicsprofessor.the famous Augustus De Morgan (1806-1871).to describean apparentmathematical discovery of his older brother Francis.While coloring the counties ofa map ofEngland,Francis Guthrie (1831-1899)observed thathecould color them2 CHAPTER 0. THE ORIGIN OF GRAPH COLORINGS .. .. .. .. .. .. .. . ..... .... ..... ... . . . ........ ...... ....... ...... ....... ...... ....... ....... ...... ....... . ... ... ... ..................... . . .. . .... .... ..... .... .... ..... .... .... ..... .... .... .. .. .. .................. ....... ... ... ... ... ...... .... ..... ................. ... ... .. ........... .......... ............................... ................................................ ................................. ................................ . . . . . . . . . . . . .. .. . . ... ... ................ ...... ...... ... ... ... ........ ................... .. .................... .. ......... . . . .. . . ....... .... ... . ...... .............. .......... ....... ................................ . .... . .. . ..... .. .. .. .. .. . .. . ..... . . .............................. ........................ ............................ ......................................................... . .. . ... ......... ... ... .. . . .................................. . . .................... .................... .............. ............................................... .. . ................. .. . ........................ ............................................................................................................ . ... .. .. .. .. .. .. .. .. ... ... ... .. ... .............. ............. . . ..... . ... ... ... ... ........ .... .. .... ... .... .................... ...... ... ... .. .. .... ... ... ........ ...... . ............ ... .. . ............ ... . ..... ... ... ..... ... . .......................... ................... ................................ . .................................................. .................................... ......................................................... .. .. ... ... .. .. ................................... ... . ..... .. .. .. ... .. .. ..... .......... . .. ................. .. ... ................................... .................... ............................................ . ................... .................... .................................................................. ... ... .... ... . ...................................... ....... ......... ... .. ... .. ... .... ......... .. ... .... .... ...... ... ..... .... ..... .. . . .......... ......... .. ... .... ..... ........ .... ... .. ..... .. ... .... ............................................ ........... .. .. .. ... .. .. ... .... ... .. ... .... ..... ... ... .. ... .. .. .. ... ...... ....... . ...................... .. .... .. . . ... . .. ... ...... .. .. . .. ... ... .. ....... .. .. . .. . . . . .... . .. . .. ..... . .. .. . ... .... .. .. ... .... .. ....... ............ ... ... ... .... ... .. .. .... .. .. . .. ... ... . .. . .. . . . ... .. ... ... ... .. .......... .... . . . .. .. . ... . .. ... . .... ............................ . .. . ..................... ........................... .. ............. ................................ ............... . ... . ....................................................... ........ .... ... ...... ......... ... .... ... ... ........ ... ............ ........ .... .... ... .. ... .. ... .. . .. . .. .. .. .. .. .. .. .. .. ... .. .. .. .. .. .... ............... ......................................... . ... ... ... .. .. ... ........ .................................................................. ... ... ... .. .. ... .. .. .. . ......................................... . ... .. ... .. ....................... .. .... .... ..... ...... ....... ............................. .. ... . ..... ..... ... ........ ................. ... ... . ... . ... .. . .... ............... ........... ........................................... ............................................................. ................ .... ... ... ... .... ....... .... ..... .. ... ... .. .. .. .. ... ... .. ...... .. .... ........ . ................ ................................... .............. .................................................................................................... ............................................................. .. ................................................................................. ..................................................... .. . ............................................... ..................................... .................... .................. . ... .. ... ... ............................ ....... ....... ...... ...... ...... ....... .... .... ... ... .... .. ... ... ... .. ............................. ................................ ............................................................................................................. ........... . . .. .. .. .. .. ... .. . Venezuela Uruguay Falkland Islands Colombia Bolivia Chile Atlantic Ocean Brazil French Guiana Guyana Suriname Ecuador Peru Pacific Ocean Argentina Paraguay Figure 1: Map of South America Many of the concepts, theorems, and problems of Graph Theory lie in the shad￾ows of the Four Color Problem. Indeed . . . Graph Theory is an area of mathematics whose past is always present. Since the maps we consider can be real or imagined, we can think of maps being divided into more general regions, rather than countries, states, provinces, or some other geographic entities. So just how did the Four Color Problem begin? It turns out that this question has a rather well-documented answer. On 23 October 1852, a student, namely Fred￾erick Guthrie (1833–1886), at University College London visited his mathematics professor, the famous Augustus De Morgan (1806–1871), to describe an apparent mathematical discovery of his older brother Francis. While coloring the counties of a map of England, Francis Guthrie (1831–1899) observed that he could color them