DISCRETE MATHEMATICS AND ITS APPLICATIONSSeriesEditorKENNETHH.ROSENCHROMATICGRAPHTHEORYGARY CHARTRANDPING ZHANGCRC)CRCPressA CHAPMANALLBOOK
PREFACEBeginning with the origin of the Four Color Problem in 1852, the field of graphcolorings has developed into one of the most popular areas of graph theory. Thisbook imtroduces graph theory with a coloring theme.It explores connections between major topics in graph theory and graph colorings, including Ramsey numbersand domination, as well as such emerging topics as list colorings, rainbow colorings.distance colorings related to the Channel Assignment Problem, and vertex/edge distinguishing colorings.Discussions of a historical, applied, and algorithmic natureare included. Each chapter in the text contains many exercises of varying levels ofdifficulty. There is also an appendix containing suggestions for study projectsThe authorsare honored tohave been invited by CRCPress to writeatextbook.Withtheelous literaturethatexists ongralh coloringsandrathe dynamic naof the subiect.we weremmediatelyfacedwiththechallengeof determining which topics to includeand,perhaps even more importantly,whichoyre.There are several instances when the same concept has been.1diedbydifferent.aunors using different terminology and different notation. Wefore required to make a number of decisions regarding terminology andwerethernotation. While nearly all mathematicians working on graph colorings use positiveintegers asas colors, there are also some who use nonnegative integers. There areinstances when colorings and labelings have been used synonymously. For the mostpart, colorings have been used when the primary goal has been either to minimizethe number of colors or the largest color (equivalently, the span of colors)Wedecided that this book should be intended forone ormore of thefllwingpurposes:. a course in graph theory with an emphasis on graph colorings, where thiscourse could beeithera beginning course ingraphtheory orafollow-up courseto an elementary graph theory course.. a reading course on graph colorings..a seminar on graph colorings.asareference book for individuals interested in graph colorings.To accomplish this, it has been our goal to write this book in an engaging, studentfriendly style so that it contains carefully explained proofs and examples and con-tains many exercises of varying difficulty.This book consists of 15 chapters (Chapters 0-14). Chapter 0 provides somebackground on the origin of graph colorings - primarily giving a discussion of theFour Color Problem. For those readers who desire a more extensive discussion of thehistory and solution of the Four Color Problem, we recommend the interesting bookbyRobin Wilson,titled Four Colors Suffice:HowtheMap Problem Was Solved.publishedbyPrincetonUniversityPress in 2002To achieve the goal of having the book self-contained, Chapters 1-5 have beenwritten to contain many of the fundamentals of graph theory that lie outside ofvii
PREFACE Beginning with the origin of the Four Color Problem in 1852, the field of graph colorings has developed into one of the most popular areas of graph theory. This book introduces graph theory with a coloring theme. It explores connections between major topics in graph theory and graph colorings, including Ramsey numbers and domination, as well as such emerging topics as list colorings, rainbow colorings, distance colorings related to the Channel Assignment Problem, and vertex/edge distinguishing colorings. Discussions of a historical, applied, and algorithmic nature are included. Each chapter in the text contains many exercises of varying levels of difficulty. There is also an appendix containing suggestions for study projects. The authors are honored to have been invited by CRC Press to write a textbook on graph colorings. With the enormous literature that exists on graph colorings and the dynamic nature of the subject, we were immediately faced with the challenge of determining which topics to include and, perhaps even more importantly, which topics to exclude. There are several instances when the same concept has been studied by different authors using different terminology and different notation. We were therefore required to make a number of decisions regarding terminology and notation. While nearly all mathematicians working on graph colorings use positive integers as colors, there are also some who use nonnegative integers. There are instances when colorings and labelings have been used synonymously. For the most part, colorings have been used when the primary goal has been either to minimize the number of colors or the largest color (equivalently, the span of colors). We decided that this book should be intended for one or more of the following purposes: • a course in graph theory with an emphasis on graph colorings, where this course could be either a beginning course in graph theory or a follow-up course to an elementary graph theory course, • a reading course on graph colorings, • a seminar on graph colorings, • as a reference book for individuals interested in graph colorings. To accomplish this, it has been our goal to write this book in an engaging, studentfriendly style so that it contains carefully explained proofs and examples and contains many exercises of varying difficulty. This book consists of 15 chapters (Chapters 0-14). Chapter 0 provides some background on the origin of graph colorings – primarily giving a discussion of the Four Color Problem. For those readers who desire a more extensive discussion of the history and solution of the Four Color Problem, we recommend the interesting book by Robin Wilson, titled Four Colors Suffice: How the Map Problem Was Solved, published by Princeton University Press in 2002. To achieve the goal of having the book self-contained, Chapters 1-5 have been written to contain many of the fundamentals of graph theory that lie outside of vii
This includes basic termraph colorings.ninologyand results,andconntivity,Eulerian and Hamiltonian graphs,matchings and factorizations, and graph'embeddings.. The remainder of the book (Chapters 6-14) deal exclusively withgraph colorings. Chapters 6 and 7 provide an introduction to vertex colorings andbounds for the chromatic number. The emphasis of Chapter 8 is vertex coloringsof graphs embedded on surfaces. Chapter 9 discusses a variety of restricted vertex colorings, including list colorings. Chapter 10 introduces edge colorings, whileChapter Il discusses monochromatic and rainbow edge colorings, including an in-troduction to Ramsey numbers. Chapter 1l also provides a discussion of the RoadColoring Problem. The main emphasis of Chapter 12 is complete vertex coloringsIn Chapter 13, several distinguishing vertex and edge colorings are described.InChapter 14many distance-related vertex colorings are introduced, some inspired bythe Channel Assignment Problem, as well as a discussion of domination in terms ofvertex coloringThere is an Appendix listing fourteen topics for those who may be interested ine independent studtwo sectionsprsiunor:horninencesathe end of the book.The first of these, titled General References, contains a list ofreferences. both for Chapter 0 and of a general nature for all succeeding chaptersThe second suc section (Bibliography) primarily contains a list of publications towhich specific referencemade in the text. Finally, there is an Index of Namelisting individuals referred to in this book, an Index of Mathematical Terms, and aList of Symbols.There arey people we wish to thank.First, our thanks to mathematicians Ken Appel, Tiziana Calamoneri,Nicolaas de Bruijn, Ermelinda DeLaVinaStephnocke, Staszek Radzizowkidwad Scmichel,obinTomas,OlivTogni, and Avraham Trahtman for kindly providing us with information and com-cating with us on some topics. Thank you as well to our friends Shashi Kapoorn11and Al Polimeni for their interest and encouragement in this project. We especiallywant to thank Bob Stern, Executive Editor of CRC Press, Taylor & Francis Group,for his constant communication, encouragement, and interest and for suggestingthis writing project to us.Finally, we thank Marsha Pronin, Project Coordinator,Samantha White, Editorial Assistant, and Jim McGovern, Project Editor for theircooperationG.C.& P.Z.vii
graph colorings. This includes basic terminology and results, trees and connectivity, Eulerian and Hamiltonian graphs, matchings and factorizations, and graph embeddings. The remainder of the book (Chapters 6-14) deal exclusively with graph colorings. Chapters 6 and 7 provide an introduction to vertex colorings and bounds for the chromatic number. The emphasis of Chapter 8 is vertex colorings of graphs embedded on surfaces. Chapter 9 discusses a variety of restricted vertex colorings, including list colorings. Chapter 10 introduces edge colorings, while Chapter 11 discusses monochromatic and rainbow edge colorings, including an introduction to Ramsey numbers. Chapter 11 also provides a discussion of the Road Coloring Problem. The main emphasis of Chapter 12 is complete vertex colorings. In Chapter 13, several distinguishing vertex and edge colorings are described. In Chapter 14 many distance-related vertex colorings are introduced, some inspired by the Channel Assignment Problem, as well as a discussion of domination in terms of vertex colorings. There is an Appendix listing fourteen topics for those who may be interested in pursuing some independent study. There are two sections containing references at the end of the book. The first of these, titled General References, contains a list of references, both for Chapter 0 and of a general nature for all succeeding chapters. The second such section (Bibliography) primarily contains a list of publications to which specific reference is made in the text. Finally, there is an Index of Names, listing individuals referred to in this book, an Index of Mathematical Terms, and a List of Symbols. There are many people we wish to thank. First, our thanks to mathematicians Ken Appel, Tiziana Calamoneri, Nicolaas de Bruijn, Ermelinda DeLaVi˜na, Stephen Locke, Staszek Radziszowski, Edward Schmeichel, Robin Thomas, Olivier Togni, and Avraham Trahtman for kindly providing us with information and communicating with us on some topics. Thank you as well to our friends Shashi Kapoor and Al Polimeni for their interest and encouragement in this project. We especially want to thank Bob Stern, Executive Editor of CRC Press, Taylor & Francis Group, for his constant communication, encouragement, and interest and for suggesting this writing project to us. Finally, we thank Marsha Pronin, Project Coordinator, Samantha White, Editorial Assistant, and Jim McGovern, Project Editor for their cooperation. G.C. & P.Z. viii
Table of Contents10. The Origin of Graph Colorings271. Introduction to Graphs271.1 Fundamental Terminology301.2 Connected Graphs331.3 Distance in Graphs371.4 Isomorphic Graphs391.5 Common Graphs and Graph Operations441.6 Multigraphs and Digraphs47Exercises for Chapter 1532. Trees and Connectivity532.1 Cut-vertices, Bridges, and Blocks562.2 Trees592.3 Connectivity and Edge-Connectivity632.4 Menger's Theorem67Exercises for Chapter 2713. Eulerian and Hamiltonian Graphs713.1 Eulerian Graphs763.2 de Brujn Digraphs793.3 Hamiltonian Graphs87Exercises for Chapter 3914. Matchings and Factorization 914.1 Matchings984.2 Independence in Graphs1004.3 Factors and Factorization106Exercises for Chapter 41095. Graph Embeddings1095.1 Planar Graphs and the Euler Identity1185.2 Hamiltonian Planar Graphsix
Table of Contents 0. The Origin of Graph Colorings 1 1. Introduction to Graphs 27 1.1 Fundamental Terminology 27 1.2 Connected Graphs 30 1.3 Distance in Graphs 33 1.4 Isomorphic Graphs 37 1.5 Common Graphs and Graph Operations 39 1.6 Multigraphs and Digraphs 44 Exercises for Chapter 1 47 2. Trees and Connectivity 53 2.1 Cut-vertices, Bridges, and Blocks 53 2.2 Trees 56 2.3 Connectivity and Edge-Connectivity 59 2.4 Menger’s Theorem 63 Exercises for Chapter 2 67 3. Eulerian and Hamiltonian Graphs 71 3.1 Eulerian Graphs 71 3.2 de Bruijn Digraphs 76 3.3 Hamiltonian Graphs 79 Exercises for Chapter 3 87 4. Matchings and Factorization 91 4.1 Matchings 91 4.2 Independence in Graphs 98 4.3 Factors and Factorization 100 Exercises for Chapter 4 106 5. Graph Embeddings 109 5.1 Planar Graphs and the Euler Identity 109 5.2 Hamiltonian Planar Graphs 118 ix
5.3 Planarity Versus Nonplanarity1201315.4 Embedding Graphs on Surfaces1395.5 The Graph Minor Theorem141Exercises for Chapter 51476. Introduction to Vertex Colorings1476.1 The Chromatic Number of a Graph1536.2 Applications of Colorings1606.3 Perfect GraphsExercises for Chapter 61707. Bounds for the Chromatic Number1757.1 Color-Critical Graphs1751797.2 Upper Bounds and Greedy Colorings1897.3 Upper Bounds and Oriented Graphs1957.4 The Chromatic Number of Cartesian Products200Exercises for Chapter 72058. Coloring Graphs on Surfaces2058.1 The Four Color Problem2088.2 The Conjectures of Hajos and Hadwiger2118.3 Chromatic Polynomials8.4 The Heawood Map-Coloring Problem217219Exercises for Chapter 82239. Restricted Vertex Colorings2239.1 Uniquely Colorable Graphs2309.2 List Colorings2409.3 Precoloring Extensions of GraphsExercises for Chapter 924524910. Edge Colorings of Graphs24910.1 The Chromatic Index and Vizing's Theorem25510.2 Class One and Class Two Graphs26210.3 Tait Colorings26910.4 Nowhere-Zero Flows27910.5 List Edge Coloringsx
5.3 Planarity Versus Nonplanarity 120 5.4 Embedding Graphs on Surfaces 131 5.5 The Graph Minor Theorem 139 Exercises for Chapter 5 141 6. Introduction to Vertex Colorings 147 6.1 The Chromatic Number of a Graph 147 6.2 Applications of Colorings 153 6.3 Perfect Graphs 160 Exercises for Chapter 6 170 7. Bounds for the Chromatic Number 175 7.1 Color-Critical Graphs 175 7.2 Upper Bounds and Greedy Colorings 179 7.3 Upper Bounds and Oriented Graphs 189 7.4 The Chromatic Number of Cartesian Products 195 Exercises for Chapter 7 200 8. Coloring Graphs on Surfaces 205 8.1 The Four Color Problem 205 8.2 The Conjectures of Haj´os and Hadwiger 208 8.3 Chromatic Polynomials 211 8.4 The Heawood Map-Coloring Problem 217 Exercises for Chapter 8 219 9. Restricted Vertex Colorings 223 9.1 Uniquely Colorable Graphs 223 9.2 List Colorings 230 9.3 Precoloring Extensions of Graphs 240 Exercises for Chapter 9 245 10. Edge Colorings of Graphs 249 10.1 The Chromatic Index and Vizing’s Theorem 249 10.2 Class One and Class Two Graphs 255 10.3 Tait Colorings 262 10.4 Nowhere-Zero Flows 269 10.5 List Edge Colorings 279 x
28210.6 Total Colorings of Graphs284Exercises for Chapter 1028911. Monochromatic and Rainbow Colorings28911.1 Ramsey Numbers29611.2 Turan's Theorem29911.3 Rainbow Ramsey Numbers11.4 Rainbow Numbers of Graphs30631411.5 Rainbow-Connected Graphs32011.6 The Road Coloring Problem324Exercises for Chapter 1132912. Complete Colorings32912.1 The Achromatic Number of a Graph33512.2 Graph Homomorphisms12.3 The Grundy Number of a Graph349356Exercises for Chapter 1235913. Distinguishing Colorings35913.1 Edge-Distinguishing Vertex Colorings37013.2 Vertex-Distinguishing Edge Colorings37913.3 Vertex-Distinguishing Vertex Colorings13.4 Neighbor-Distinguishing Edge Colorings385391Exercises for Chapter 1339714. Colorings, Distance, and Domination39714.1 T-Colorings14.2 L(2,1)-Colorings40314.3 Radio Colorings410-41714.4 Hamiltonian Colorings42514.5 Domination and Colorings43414.6EpilogueExercises for Chapter 14434加编锅5#Appendix: Study ProjectsGeneral ReferencesBibliographyIndex (Names and Mathematical Terms)List of Symbolsxi
10.6 Total Colorings of Graphs 282 Exercises for Chapter 10 284 11. Monochromatic and Rainbow Colorings 289 11.1 Ramsey Numbers 289 11.2 Tur´an’s Theorem 296 11.3 Rainbow Ramsey Numbers 299 11.4 Rainbow Numbers of Graphs 306 11.5 Rainbow-Connected Graphs 314 11.6 The Road Coloring Problem 320 Exercises for Chapter 11 324 12. Complete Colorings 329 12.1 The Achromatic Number of a Graph 329 12.2 Graph Homomorphisms 335 12.3 The Grundy Number of a Graph 349 Exercises for Chapter 12 356 13. Distinguishing Colorings 359 13.1 Edge-Distinguishing Vertex Colorings 359 13.2 Vertex-Distinguishing Edge Colorings 370 13.3 Vertex-Distinguishing Vertex Colorings 379 13.4 Neighbor-Distinguishing Edge Colorings 385 Exercises for Chapter 13 391 14. Colorings, Distance, and Domination 397 14.1 T-Colorings 397 14.2 L(2, 1)-Colorings 403 14.3 Radio Colorings 410 14.4 Hamiltonian Colorings 417 14.5 Domination and Colorings 425 14.6 Epilogue 434 Exercises for Chapter 14 434 Appendix: Study Projects 439 General References 446 Bibliography 453 Index (Names and Mathematical Terms) 465 List of Symbols 480 xi
Chapter 0The Origin of GraphColoringsIf the countries in a map of South America (see Figure 1) were to be colored in sucha way that every two countries with a common boundary are colored differently,then this map could be colored using only four colors. Is this true of every map?While it is not difficult to color a map of South America with four colors, it isnotpossibletocolorthisrnap with less than four colors. In fact, every two of Brazil,Argentina, Bolivia, and Paraguay are neighboring countries and so four colors arerequired to color only these fotafreIt is probably clear why we might want two countries coloreddifferentlyiftheyhaveaotheycan beeasilydistinguished asdifferent counboundarwbecear,owver,whywewoudthnkthatforcootriese map. It may notwould be enought the countries of every map. After all, we can probablyorenvisionacomplicatedmaphavinga largenumber of countrieswith somecountrieshaving several neighboring countries, so constructed that a great many colors mightpossibly be needed to color the entire map. Here we understand neighboring coun-tries to mean two countries with a boundary line in common,not simply a singlepoint in commoWhile this problem may seem nothing more than a curiosity, it is precisely thisproblem that would prove to intrigue somanyfor so long and whose attemptedsolutions would contribute so significantly to the development of the area of math.ematics known as Graph Theory and especially to the subiect of graph coloringsChromatic Graph Theory.This map coloring problem would eventually acquire aname that would become known throughout the mathematical world.The Four Color Problem Can the countries of every map be colored with fouror fewer colors so that every two countries with a common boundary are coloreddifferently?1
Chapter 0 The Origin of Graph Colorings If the countries in a map of South America (see Figure 1) were to be colored in such a way that every two countries with a common boundary are colored differently, then this map could be colored using only four colors. Is this true of every map? While it is not difficult to color a map of South America with four colors, it is not possible to color this map with less than four colors. In fact, every two of Brazil, Argentina, Bolivia, and Paraguay are neighboring countries and so four colors are required to color only these four countries. It is probably clear why we might want two countries colored differently if they have a common boundary – so they can be easily distinguished as different countries in the map. It may not be clear, however, why we would think that four colors would be enough to color the countries of every map. After all, we can probably envision a complicated map having a large number of countries with some countries having several neighboring countries, so constructed that a great many colors might possibly be needed to color the entire map. Here we understand neighboring countries to mean two countries with a boundary line in common, not simply a single point in common. While this problem may seem nothing more than a curiosity, it is precisely this problem that would prove to intrigue so many for so long and whose attempted solutions would contribute so significantly to the development of the area of mathematics known as Graph Theory and especially to the subject of graph colorings: Chromatic Graph Theory. This map coloring problem would eventually acquire a name that would become known throughout the mathematical world. The Four Color Problem Can the countries of every map be colored with four or fewer colors so that every two countries with a common boundary are colored differently? 1
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 them
2 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 shadows 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 Frederick 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
3withfours,which led him to conjecturethat no more than four colors wouldrolobe needed to color the regions of any map.The Four Color Conjecture The regions of every map can be colored with fouor fewer colors in such a way that every two regions sharing a common boundaryare colored differently.Two years earlier, in 1850, Francis had earned a Bachelor of Arts degree fromUniversity College London and then a Bachelor of Laws degree in 1852.He wouldlaterbecomea mathematics professorhimself at the University of CapeTown inSouth Africa.Francis developed a lifelong interest in botanyand his extensivecollection of flora from the Cape Peninsula would later be placed in the GuthrieHerbarium in the University of Cape Town Botany Department. Several rare speciesof floraarenamed forhimFrancis Guthrie attempted to prove the Four Color Conjecturd althoughhethought he may havebeen successful, hewasnotcompletely satisfied withhisproofFrancis discussed his discovery with Frederick. With Francis' approval, Frederickmentioned the statement ofhisapparenttheoremtoProfessorr De Morgan, whoexpressed pleasure with it and believed it to be a new result. Evidently Frederickasked Professor De Morgan if he was aware of an argument that would establishthe truth of the theorem.This led De Morgan to write a letter to his friend, the famous Irish mathematician Sir William Rowan Hamilton (1805-1865) in Dublin. These two mathematicalgiants had corresponded for years, although apparently had met only once. De Morgan wrote (in part):My dear Hamilton:A student of mine asked me to day to give him a reason for a factwhich I did not know was a fact-and do not yet.He says that if afigure be any how divided and the compartments differently coloured sothat figures with any portion of common boundary lines are differentlycoloured - four colours may be wanted but not more - the following ishis case in which four are wanted.ABCD arenames ofcoloursQuery cannot a necessity for five or more be invented ...My pupil says he guessed it colouring a map of England ..Themore I think of it the more evident it seems. If you retort with sovery simple case which makes me out a stupid animal, I think I must doas the Sphynr did
3 with four colors, which led him to conjecture that no more than four colors would be needed to color the regions of any map. The Four Color Conjecture The regions of every map can be colored with four or fewer colors in such a way that every two regions sharing a common boundary are colored differently. Two years earlier, in 1850, Francis had earned a Bachelor of Arts degree from University College London and then a Bachelor of Laws degree in 1852. He would later become a mathematics professor himself at the University of Cape Town in South Africa. Francis developed a lifelong interest in botany and his extensive collection of flora from the Cape Peninsula would later be placed in the Guthrie Herbarium in the University of Cape Town Botany Department. Several rare species of flora are named for him. Francis Guthrie attempted to prove the Four Color Conjecture and although he thought he may have been successful, he was not completely satisfied with his proof. Francis discussed his discovery with Frederick. With Francis’ approval, Frederick mentioned the statement of this apparent theorem to Professor De Morgan, who expressed pleasure with it and believed it to be a new result. Evidently Frederick asked Professor De Morgan if he was aware of an argument that would establish the truth of the theorem. This led De Morgan to write a letter to his friend, the famous Irish mathematician Sir William Rowan Hamilton (1805–1865) in Dublin. These two mathematical giants had corresponded for years, although apparently had met only once. De Morgan wrote (in part): My dear Hamilton: A student of mine asked me to day to give him a reason for a fact which I did not know was a fact – and do not yet. He says that if a figure be any how divided and the compartments differently coloured so that figures with any portion of common boundary lines are differently coloured – four colours may be wanted but not more – the following is his case in which four are wanted. .. ... .... ...... ....... .............. ............. ......... ........ ..... .... ... ... . .. ... ... .... .... ....... ........ .............. ................ .......... ... ........ ....... ..... .... ... .. .... A B C A B C D are D names of colours Query cannot a necessity for five or more be invented . . . My pupil says he guessed it colouring a map of England . . .. The more I think of it the more evident it seems. If you retort with some very simple case which makes me out a stupid animal, I think I must do as the Sphynx did . .
CHAPTER 0.THE ORIGIN OF GRAPH COLORINGSIn De Morgan's lettertoHamilton, he refersto the"Sphynx"(or Sphinx).Whilethe Sphinx is a male statue of a lion with the head of a human in ancient Egyptwhich guards the entrance to a temple, the Greek Sphinx is a female creature ofbad luck who sat atop a rock posing the following riddle to all those who pass by:What animal is that which in the morning goes on four fet, at noon ontwo, and in the evening upon three?Thoswho did not solve the riddle were killed. Only Oedipus (the titcharactein Oedipus Rer by Sophocles, a play about how people do not control their owndestiny) answered the riddle corectly as"Man'whoin childhood (the morning oflife) creeps on hands and knees, in manhood (thenoon of life) walks upright, andin old age (the evening of life) walks with the aid of a cane. Upon learning that herriddle had been solved, the Sphinx cast herself from the rock and perished, a fateDe Morgan had envisioned for himselfifhis riddle (the Four Color Problem) hadan easy and immediate solution.In De Morgan's letter to Hamilton, De Morgan attempted to explain why theproblem appeared to be difficult. He followed this explanation by writing:But it is tricky work and I am not sure of all convolutions-What doyou say? And has it, if true been noticed?Among Hamilton's numerousmathematical accomplishments was his remarkable work with quaternions.Hamilton's quaternions are a 4-dimensional svstem ofnumbers of the form a + bi + cj + dk, where a,b,c, d e R and ,? = j2-2-When c- 0.these numbers are the 2-dimensional system of complex nunberswhile when b= d - 0, these numbers are simply real numbers. Although it isnonplace for binary operations in algebraic structures to be commutative, suchis not the case for products of quaternions. For example, i. j = k but j -i - -h.Since De Morgan had shown an interest in Hamilton's research on quaternions aswell asother subjects Hamilton had studied itislikely that De Morgan expectedI enthusiastic reply to his letter to Hamilton.Such was not the case, however.Indeed, on 26 October 1852, Hamilton gave a quick but unexpected response:I am not likely to attempt your “quaternion" of colours very soon.Hamilton's response did nothing however to diminish De Morgan's interest in theFourColorProbleSince De Morgan's letter to Hamilton did not mention Frederick Guthrie byname, there may bereason to question whether Frederick was in fact the studento whom De Morgan was referring and that it was Frederick's older brother Franciswhowasthe originatorof theFour Color ProblemIn 1852Frederick Guthrie was a teenager.He would go on to become a distinguished physics professor and founder of the Physical Society in Londor.Anareathat he studied is the scienceof thermionic emission-firstreported byFrederickGuthrie in 1873. He discovered that a red-hot iron sphere with a positive charge
4 CHAPTER 0. THE ORIGIN OF GRAPH COLORINGS In De Morgan’s letter to Hamilton, he refers to the “Sphynx” (or Sphinx). While the Sphinx is a male statue of a lion with the head of a human in ancient Egypt which guards the entrance to a temple, the Greek Sphinx is a female creature of bad luck who sat atop a rock posing the following riddle to all those who pass by: What animal is that which in the morning goes on four feet, at noon on two, and in the evening upon three? Those who did not solve the riddle were killed. Only Oedipus (the title character in Oedipus Rex by Sophocles, a play about how people do not control their own destiny) answered the riddle correctly as “Man”, who in childhood (the morning of life) creeps on hands and knees, in manhood (the noon of life) walks upright, and in old age (the evening of life) walks with the aid of a cane. Upon learning that her riddle had been solved, the Sphinx cast herself from the rock and perished, a fate De Morgan had envisioned for himself if his riddle (the Four Color Problem) had an easy and immediate solution. In De Morgan’s letter to Hamilton, De Morgan attempted to explain why the problem appeared to be difficult. He followed this explanation by writing: But it is tricky work and I am not sure of all convolutions – What do you say? And has it, if true been noticed? Among Hamilton’s numerous mathematical accomplishments was his remarkable work with quaternions. Hamilton’s quaternions are a 4-dimensional system of numbers of the form a + bi + cj + dk, where a, b, c, d ∈ R and i 2 = j 2 = k 2 = −1. When c = d = 0, these numbers are the 2-dimensional system of complex numbers; while when b = c = d = 0, these numbers are simply real numbers. Although it is commonplace for binary operations in algebraic structures to be commutative, such is not the case for products of quaternions. For example, i · j = k but j · i = −k. Since De Morgan had shown an interest in Hamilton’s research on quaternions as well as other subjects Hamilton had studied, it is likely that De Morgan expected an enthusiastic reply to his letter to Hamilton. Such was not the case, however. Indeed, on 26 October 1852, Hamilton gave a quick but unexpected response: I am not likely to attempt your “quaternion” of colours very soon. Hamilton’s response did nothing however to diminish De Morgan’s interest in the Four Color Problem. Since De Morgan’s letter to Hamilton did not mention Frederick Guthrie by name, there may be reason to question whether Frederick was in fact the student to whom De Morgan was referring and that it was Frederick’s older brother Francis who was the originator of the Four Color Problem. In 1852 Frederick Guthrie was a teenager. He would go on to become a distinguished physics professor and founder of the Physical Society in London. An area that he studied is the science of thermionic emission – first reported by Frederick Guthrie in 1873. He discovered that a red-hot iron sphere with a positive charge