《图论》课程教学资源（书籍文献）Chromatic Graph Theory（GARY CHARTRAND，Ping Zhang）

20CHAPTER0.THEORIGINOFGRAPHCOLORINGSto Hermann Weyl, a gifted mathematician who was a colleague of Albert Einsteinand a student of the famous mathematician David Hilbert (1862-1943), whom hereplaced as mathematics chair at the University of Gottingen. In 1900, Hilbert gavealecture beforetheInternational Congress of Mathematicians in Paris in which hepresented 23 extremely challenging problems.In 1935,Heesch solved one of theseproblems (Problem 18)dealing with tilings of the plane. One of Heesch's friends atGottingen was Ernst Witt (1911-1991), who thought he had solved an even morefamousproblem:theFour ColorProblem:Witt wasanxiousto showhisproof tothe famous German mathematician Richard Courant (1888-1972),who later movedto the United Statesand founded the Courant Institute of Mathematical Sciences.Since Courantwasintheprocess of leavingGottingen forBerlin,Heesch joinedWitt to travel with Courant by train in order to describe the proof. However,Courant was not convinced and the disappointed young mathematicians returnedto Gottingen. On their return trip, however,Heesch discovered an error in Witt'sproof.Heesch toohad become captivated by theFour Color Problem.As Heesch studied this famous problem,he had become increasingly convincedthat the problem could be solved by finding an unavoidable set of reducible con-figurations, even though such a set mavery well be extremelylarge.He beganlecturing on his ideas in the 1940s at the Universities of Hamburg and Kiel.A1948 lecture at the University of Kiel was attended by the student Wolfgang Haken(born in 1928), who recalls Heesch saying that an unavoidable set of reducible con-figurations may contain as many as ten thousand members. Heesch discovered amethod for creating many unavoidable sets of configurations. Since the method hadan electrical flavor to it, electrical terms were chosen for the resulting terminology.What Heesch did was to consider the dual planar graphs constructed from cubicmaps.Thus the configurations of regions in a cubic map became configurations ofvertices in the resulting dual planar graph. These planar graphs themselves hadregions, each necessarily a triangle (a 3-gon).Since the only cubic maps whosecoloring was still in question were those in which every region was surrounded byfive or more neighboring regions, five or more edges of the resulting planar graphmet at each vertex of the graph. If k edges meet at a vertex, then the vertex is saidto have degree k.Thus every vertex in each planar graph of interesthad degree 5or more.Heesch then assigned each vertex in the graph a"charge"of 6-k if thedegree of thevertexwask(seeChapter 5).The only verticesreceiving apositivecharge were therefore those of degree5, which were given a charge of +1. Thevertices of degree 6 had a charge of 0, those of degree 7 a charge of -1, and so on.It can be proved (see Chapter 5)that the sum of the charges of the vertices in sucha planar graph is always positive (in fact exactly 12).Heesch's plan consisted of establishing rules, called discharging rules, for movinga positive charge from one vertex to others in a manner that did not change thesum of the charges. The goal was to use these rules to create an unavoidable setof configurations by showing that if a minimum counterexample to the Four ColorConjecture contained none of these configurations, then the sum of the charges ofits verticeswasnot12.Since Heesch's discharging method was successful in finding unavoidable sets

20 CHAPTER 0. THE ORIGIN OF GRAPH COLORINGS to Hermann Weyl, a gifted mathematician who was a colleague of Albert Einstein and a student of the famous mathematician David Hilbert (1862–1943), whom he replaced as mathematics chair at the University of G¨ottingen. In 1900, Hilbert gave a lecture before the International Congress of Mathematicians in Paris in which he presented 23 extremely challenging problems. In 1935, Heesch solved one of these problems (Problem 18) dealing with tilings of the plane. One of Heesch’s friends at G¨ottingen was Ernst Witt (1911–1991), who thought he had solved an even more famous problem: the Four Color Problem. Witt was anxious to show his proof to the famous German mathematician Richard Courant (1888–1972), who later moved to the United States and founded the Courant Institute of Mathematical Sciences. Since Courant was in the process of leaving G¨ottingen for Berlin, Heesch joined Witt to travel with Courant by train in order to describe the proof. However, Courant was not convinced and the disappointed young mathematicians returned to G¨ottingen. On their return trip, however, Heesch discovered an error in Witt’s proof. Heesch too had become captivated by the Four Color Problem. As Heesch studied this famous problem, he had become increasingly convinced that the problem could be solved by finding an unavoidable set of reducible con- figurations, even though such a set may very well be extremely large. He began lecturing on his ideas in the 1940s at the Universities of Hamburg and Kiel. A 1948 lecture at the University of Kiel was attended by the student Wolfgang Haken (born in 1928), who recalls Heesch saying that an unavoidable set of reducible con- figurations may contain as many as ten thousand members. Heesch discovered a method for creating many unavoidable sets of configurations. Since the method had an electrical flavor to it, electrical terms were chosen for the resulting terminology. What Heesch did was to consider the dual planar graphs constructed from cubic maps. Thus the configurations of regions in a cubic map became configurations of vertices in the resulting dual planar graph. These planar graphs themselves had regions, each necessarily a triangle (a 3-gon). Since the only cubic maps whose coloring was still in question were those in which every region was surrounded by five or more neighboring regions, five or more edges of the resulting planar graph met at each vertex of the graph. If k edges meet at a vertex, then the vertex is said to have degree k. Thus every vertex in each planar graph of interest had degree 5 or more. Heesch then assigned each vertex in the graph a “charge” of 6 − k if the degree of the vertex was k (see Chapter 5). The only vertices receiving a positive charge were therefore those of degree 5, which were given a charge of +1. The vertices of degree 6 had a charge of 0, those of degree 7 a charge of −1, and so on. It can be proved (see Chapter 5) that the sum of the charges of the vertices in such a planar graph is always positive (in fact exactly 12). Heesch’s plan consisted of establishing rules, called discharging rules, for moving a positive charge from one vertex to others in a manner that did not change the sum of the charges. The goal was to use these rules to create an unavoidable set of configurations by showing that if a minimum counterexample to the Four Color Conjecture contained none of these configurations, then the sum of the charges of its vertices was not 12. Since Heesch’s discharging method was successful in finding unavoidable sets

21much of theearlywork inthe20thcenturyontheFour ColorProblemwasfocusedon showing that certain configurations were reducible. Often showing that even oneconfigurationwasreduciblebecame amonumentaltask.Inthe1960sHeeschhadstreamlined Birkhoff's approach of establishing the reducibility of certain configu-rations.One of these techniques, called D-reduction, was sufficiently algorithmicin nature to allow this technique to be executed on a computer and, in fact, acomputer program for implementingD-reducibility was written on the CDC1604Acomputer by Karl Dirre, a graduate of Hanover.Because of the large number of ways that the vertices on the ring of a configu-ration could be colored,theamount of computer time needed to analyze complexconfigurations became a major barrierto their work. Heesch was then ableto de-velop a new method, called C-reducibility, where only some of the colorings of thering vertices needed to be considered. Of course, one possible way to deal with theobstacles that Heesch and Dirrewerefacing was tofind a morepowerful computeron which to run Dirre'sprogram.While Haken had attended Heesch's talk at the University of Kiel on the FourColorProblem,thelecturesthat seemed tointerestHakenthemost werethoseontopology given by Karl Heinrich Weise in which he described three long-standingunsolved problems.One of these was thePoincare Conjectureposed bythegreatmathematician and physicist Henri Poincare in 1904 and which concerned the rela-tionship of shapes, spaces,and surfaces.Another wastheFour ColorProblem andthe third was a problem in knot theory. Haken decided to attempt to solve all threeproblems. Although his attempts to prove thePoincare Conjecture failed, he wassuccessful with the knot theory problem.A proof of the Poincare Conjecture by theRussian mathematician Grigori Perelman was confirmed and reported in Trieste,Italyon17June2006.For this accomplishment,he wasawarded aFields Medal(themathematical equivalent of the Nobel Prize) on 22August 2006.However,Perelman declined to attend the ceremony and did not accept the prize. As for theFour Color Problem, the story continues.Haken's solution of the problem in knot theory led to his being invited to theUniversity of Illinois as a visiting professor. After leaving the University of Illinoisto spend some time at the Institute for Advanced Study in Princeton, Haken thenreturned to the University of Illinois to take a permanent position.Heesch inquired, through Haken, about the possibility of using the new super-computer at the University of Illinois (the ILLAC IV) but much time was stillneeded to complete its construction. The Head of the Department of ComputerScience there suggested that Heesch contact Yoshio Shimamoto, Head of the Ap-plied Mathematics Department at the Brookhaven Laboratory at the the UnitedStates Atomic Energy Commission, which had access to the Stephen Cray-designedControl Data 6600, which was thefastest computerat that time.Shimamoto himself had an interest in theFour ColorProblem and had eventhought of writing his own computer program to investigate the reducibility of con-figurations.ShimamotoarrangedforHeeschand DirretovisitBrookhaveninthelate1960s.Diuirrewasableto testmanconfigurationsforreducibility.Theconfigurations that were now known to be D-reducible still did not constitute an

21 much of the early work in the 20th century on the Four Color Problem was focused on showing that certain configurations were reducible. Often showing that even one configuration was reducible became a monumental task. In the 1960s Heesch had streamlined Birkhoff’s approach of establishing the reducibility of certain configu￾rations. One of these techniques, called D-reduction, was sufficiently algorithmic in nature to allow this technique to be executed on a computer and, in fact, a computer program for implementing D-reducibility was written on the CDC 1604A computer by Karl D¨urre, a graduate of Hanover. Because of the large number of ways that the vertices on the ring of a configu￾ration could be colored, the amount of computer time needed to analyze complex configurations became a major barrier to their work. Heesch was then able to de￾velop a new method, called C-reducibility, where only some of the colorings of the ring vertices needed to be considered. Of course, one possible way to deal with the obstacles that Heesch and D¨urre were facing was to find a more powerful computer on which to run D¨urre’s program. While Haken had attended Heesch’s talk at the University of Kiel on the Four Color Problem, the lectures that seemed to interest Haken the most were those on topology given by Karl Heinrich Weise in which he described three long-standing unsolved problems. One of these was the Poincar´e Conjecture posed by the great mathematician and physicist Henri Poincar´e in 1904 and which concerned the rela￾tionship of shapes, spaces, and surfaces. Another was the Four Color Problem and the third was a problem in knot theory. Haken decided to attempt to solve all three problems. Although his attempts to prove the Poincar´e Conjecture failed, he was successful with the knot theory problem. A proof of the Poincar´e Conjecture by the Russian mathematician Grigori Perelman was confirmed and reported in Trieste, Italy on 17 June 2006. For this accomplishment, he was awarded a Fields Medal (the mathematical equivalent of the Nobel Prize) on 22 August 2006. However, Perelman declined to attend the ceremony and did not accept the prize. As for the Four Color Problem, the story continues. Haken’s solution of the problem in knot theory led to his being invited to the University of Illinois as a visiting professor. After leaving the University of Illinois to spend some time at the Institute for Advanced Study in Princeton, Haken then returned to the University of Illinois to take a permanent position. Heesch inquired, through Haken, about the possibility of using the new super￾computer at the University of Illinois (the ILLAC IV) but much time was still needed to complete its construction. The Head of the Department of Computer Science there suggested that Heesch contact Yoshio Shimamoto, Head of the Ap￾plied Mathematics Department at the Brookhaven Laboratory at the the United States Atomic Energy Commission, which had access to the Stephen Cray-designed Control Data 6600, which was the fastest computer at that time. Shimamoto himself had an interest in the Four Color Problem and had even thought of writing his own computer program to investigate the reducibility of con- figurations. Shimamoto arranged for Heesch and D¨urre to visit Brookhaven in the late 1960s. D¨urre was able to test many more configurations for reducibility. The configurations that were now known to be D-reducible still did not constitute an

22CHAPTER0.THEORIGINOFGRAPHCOLORINGSunavoidable set,however,and Heesch and Dirre returned to Germany.In Augustof 1970 Heesch visited Brookhaven again -this time with Haken visiting the fol-lowingmonth.Attheend ofSeptember,Shimamotowasabletoshowthatifacertain configuration that he constructed (known as the horseshoe configuration)was D-reducible.then the Four Color Conjectureis true.Figure 17 shows the dualplanar graph constructed from the horseshoe configuration. This was an amazingdevelopment. To make matters even more interesting, Heesch recognized the horse-shoeconfiguration as onethathad earlierbeen shown tobe D-reducible.Because ofthe importance of knowing,with complete certainty,that this configuration was D.reducible, Shimamoto took the cautious approach of having a totally new computerprogram written to verify the D-reducibility of the horseshoe configuration.Figure17:The ShimamotohorseshoeDirre was brought back from Germany because of the concern that the originalverification of the horseshoe configuration being D-reducible might be incorrect.Also, the printout of the computer run of this was nowhere to be found. Finally,thenewcomputerprogramwasrun and, after 26hours,theprogram concludedthat this configuration was not D-reducible. It was not only that this developmentwas so very disappointing to Shimamotobut.despitethecarehetook,rumorshadbeguntocirculateinOctoberof1971thattheFourColorProblemhadbeensolved-usingacomputer!Haken had carefully checked Shimamoto's mathematical reasoning and found itto be totally correct. Consequently,fora certain period, the only obstacle standingin the way of a proof of the Four Color Conjecture had been a computer. WilliamT.Tutte (1917-2002)and Hassler Whitney (1907-1989),two of the great graphtheorists at that time, had also studied Shimamoto's method of proof and foundno flaw in his reasoning.Because this would have resulted in a far simpler proof ofthe Four Color Conjecturethan could reasonably be expected, Tutte and Whitneyconcluded that the original computer result must be wrong. However, the involve-ment of Tutte and Whitney in the Four Color Problem resulted in a clarificationof D-reducibility. Also because of their stature in the world of graph theory, therewaseven more interestin theproblem

22 CHAPTER 0. THE ORIGIN OF GRAPH COLORINGS unavoidable set, however, and Heesch and D¨urre returned to Germany. In August of 1970 Heesch visited Brookhaven again – this time with Haken visiting the fol￾lowing month. At the end of September, Shimamoto was able to show that if a certain configuration that he constructed (known as the horseshoe configuration) was D-reducible, then the Four Color Conjecture is true. Figure 17 shows the dual planar graph constructed from the horseshoe configuration. This was an amazing development. To make matters even more interesting, Heesch recognized the horse￾shoe configuration as one that had earlier been shown to be D-reducible. Because of the importance of knowing, with complete certainty, that this configuration was D￾reducible, Shimamoto took the cautious approach of having a totally new computer program written to verify the D-reducibility of the horseshoe configuration. . . . . . ............................................................... .......................................................... ....................... ............................. ......................................... . ............................................ . . . . . . ...... .... ... .... .. .............................................................................. ........................................................................... .. . . . . . . . . . . . . . . . . . . .................................................................................. . ......................................................................... .................................................................................... .... ....... ..... ......................... .................... ...... ............ ......... ........ ....... ....... ..... ...... .... .... .... ... ... .. .. .. .. . . . . .. .. .. .. ... ... .... .... ..... ...... ..... ....... ....... ........ .......... .............. ............. ................ . . .. .. .. .... .... ...... ..... ........ .......... ...................... ............. ............. ........ ....... ...... .... ... ... .. .. . . .............................................................................................................................. . r r r r r r r r r r r r r r r r r r r r r r Figure 17: The Shimamoto horseshoe D¨urre was brought back from Germany because of the concern that the original verification of the horseshoe configuration being D-reducible might be incorrect. Also, the printout of the computer run of this was nowhere to be found. Finally, the new computer program was run and, after 26 hours, the program concluded that this configuration was not D-reducible. It was not only that this development was so very disappointing to Shimamoto but, despite the care he took, rumors had begun to circulate in October of 1971 that the Four Color Problem had been solved – using a computer! Haken had carefully checked Shimamoto’s mathematical reasoning and found it to be totally correct. Consequently, for a certain period, the only obstacle standing in the way of a proof of the Four Color Conjecture had been a computer. William T. Tutte (1917–2002) and Hassler Whitney (1907–1989), two of the great graph theorists at that time, had also studied Shimamoto’s method of proof and found no flaw in his reasoning. Because this would have resulted in a far simpler proof of the Four Color Conjecture than could reasonably be expected, Tutte and Whitney concluded that the original computer result must be wrong. However, the involve￾ment of Tutte and Whitney in the Four Color Problem resulted in a clarification of D-reducibility. Also because of their stature in the world of graph theory, there was even more interest in the problem

23It would not be hard to present the history of graph theory as an accountof the struggle to prove the four color conjecture, or at least to find outwhytheproblemisdifficult.William T. Tutte (1967)IntheApril1,1975issueof the magazine Scientific Americanthepopular math-ematicswriterMartinGardner(bornin1914)stunnedthemathematicalcommunity(at least momentarily)when he wrote an articletitled Sir sensational discoveriesthat somehow have escaped public attention that contained a map (see Figure 18)advertised as one that could not be colored with four colors. However, several indi-viduals found that this map could in fact be colored with four colors, only to learnthat Gardner had intended this article as an April Fool's joke.Figure 18: Martin Gardner's April Fool's MapIn the meantime, Haken had been losing faith in a computer-aided solution of theFour Color Problem despite the fact that he had a doctoral student at the Universityof Illinois whose research was related to the problem.One of the members of thisstudent's thesis committee was Kenneth Appel (born in 1932).After completinghis undergraduate degree at Queens College with a special interest in actuarialmathematics, Appel worked at an insurance company and shortly afterwards wasdrafted and began a period of military service. He then went to the University ofMichigan for his graduate studies in mathematics. During the spring of 1956, theUniversity of Michigan acquired an IBM 650 and the very first programming courseoffered at the university was taught by John W.Carr, IIl, one of the pioneers ofcomputer education in the United States..Curiously,Carr'sdoctoral advisorattheMassachusettsInstituteof TechnologwasPhillipFranklin,who,aswementionedwrote his dissertation on the Four Color Problem.Appel audited this programming

23 It would not be hard to present the history of graph theory as an account of the struggle to prove the four color conjecture, or at least to find out why the problem is difficult. William T. Tutte (1967) In the April 1, 1975 issue of the magazine Scientific American the popular math￾ematics writer Martin Gardner (born in 1914) stunned the mathematical community (at least momentarily) when he wrote an article titled Six sensational discoveries that somehow have escaped public attention that contained a map (see Figure 18) advertised as one that could not be colored with four colors. However, several indi￾viduals found that this map could in fact be colored with four colors, only to learn that Gardner had intended this article as an April Fool’s joke. .................................................................................................................................................................................................................................................................................................... .............................................................................................................................................................................................................................................................................................................................................. ........................................................................................................................................................................................................................................................................................................................ ........................................................................................................................................................................................................................................................................ ..................................................................................................................................................................................................................................................................................................................................................................... ................................................................................................................................................................................... ................................................................................................................................................................................................................................ Figure 18: Martin Gardner’s April Fool’s Map In the meantime, Haken had been losing faith in a computer-aided solution of the Four Color Problem despite the fact that he had a doctoral student at the University of Illinois whose research was related to the problem. One of the members of this student’s thesis committee was Kenneth Appel (born in 1932). After completing his undergraduate degree at Queens College with a special interest in actuarial mathematics, Appel worked at an insurance company and shortly afterwards was drafted and began a period of military service. He then went to the University of Michigan for his graduate studies in mathematics. During the spring of 1956, the University of Michigan acquired an IBM 650 and the very first programming course offered at the university was taught by John W. Carr, III, one of the pioneers of computer education in the United States. Curiously, Carr’s doctoral advisor at the Massachusetts Institute of Technology was Phillip Franklin, who, as we mentioned, wrote his dissertation on the Four Color Problem. Appel audited this programming

24CHAPTER0.THEORIGINOFGRAPHCOLORINGScourse. Since the university did not offer summer financial support to Appel andDouglas Aircraft was recruiting computer programmers, he spent the summer of1956writing computer programs concerning theDC-8 jetliner, which was beingdesigned at the time. Appel had become hooked on computers.Kenneth Appel's area of research was mathematical logic.In fact,Appel askedHaken to give a talk at the logic seminar in the Department of Mathematics so hecould better understand the thesis. In his talk, Haken included a discussion of thecomputer difficulties that had been encountered in his approach to solve theFourColor Problem and explained that he was finished with the problem for the present.Appel,however,with hisknowledge of computer programming,convincedHakenthat the two of them should "take a shot at it"Together, Appel and Haken took a somewhat different approach. They devisedan algorithm that tested for"reduction obstacles". The work of Appel and Hakenwas greatly aided by Appel's doctoral student John Koch who wrote a very efficientprogram that tested certain kinds of configurations for reducibility.Much of Appeland Haken's work involved refining Heesch's method for finding an unavoidable setof reducible configurations.The partnership in the developing proof concerned the active involvement of ateam of three, namely Appel, Haken, and a computer. As their work progressed,Appel and Haken needed ever-increasing amounts of time on a computer. Becauseof Appel's political skills, he was able to get time on the IBM 370-168 located inthe University's administration buildingEventually,everythingpaid off.InJuneof 1976, Appel and Haken had counavoidablesetof1936reduciblenstruicteda:configurations,which was lateredtc1482Theproofwasfinallyannouncedat the 1976Summer Meeting of theAn Mathematical Society and the Math-ematical Association of America at the University of Toronto.Shortly afterwards,the University of Illinois employed the postmarkFOURCOLORSSUFFICEon its outgoing mail.In1977Frank Harary (1921-2005),editor-in-chief of thenewlyfounded Journalof Graph Theory,asked WilliamTutte if he would contribute somethingfor the firstvolume of the journal in connection with this announcement.Tutte responded witha short but pointed poem (employing his often-used pen-name Blanche Descartes)withtheunderstated title SomeRecentProgress in Combinatorics:Wolfgang HakenSmote the KrakenOne! Two! Three! Four!Quoth he:"The monster is no more".In the poem, Tutte likened theFour Color Problem to the legendary sea monsterknown as a kraken and proclaimed that Haken (along with Appel, of course) hadslain this monster.With so many mistaken beliefs that the Four Color Theorem had been provedduring the preceding century, it was probably not surprising that the announced

24 CHAPTER 0. THE ORIGIN OF GRAPH COLORINGS course. Since the university did not offer summer financial support to Appel and Douglas Aircraft was recruiting computer programmers, he spent the summer of 1956 writing computer programs concerning the DC-8 jetliner, which was being designed at the time. Appel had become hooked on computers. Kenneth Appel’s area of research was mathematical logic. In fact, Appel asked Haken to give a talk at the logic seminar in the Department of Mathematics so he could better understand the thesis. In his talk, Haken included a discussion of the computer difficulties that had been encountered in his approach to solve the Four Color Problem and explained that he was finished with the problem for the present. Appel, however, with his knowledge of computer programming, convinced Haken that the two of them should “take a shot at it”. Together, Appel and Haken took a somewhat different approach. They devised an algorithm that tested for “reduction obstacles”. The work of Appel and Haken was greatly aided by Appel’s doctoral student John Koch who wrote a very efficient program that tested certain kinds of configurations for reducibility. Much of Appel and Haken’s work involved refining Heesch’s method for finding an unavoidable set of reducible configurations. The partnership in the developing proof concerned the active involvement of a team of three, namely Appel, Haken, and a computer. As their work progressed, Appel and Haken needed ever-increasing amounts of time on a computer. Because of Appel’s political skills, he was able to get time on the IBM 370-168 located in the University’s administration building. Eventually, everything paid off. In June of 1976, Appel and Haken had constructed an unavoidable set of 1936 reducible configurations, which was later reduced to 1482. The proof was finally announced at the 1976 Summer Meeting of the American Mathematical Society and the Math￾ematical Association of America at the University of Toronto. Shortly afterwards, the University of Illinois employed the postmark FOUR COLORS SUFFICE on its outgoing mail. In 1977 Frank Harary (1921–2005), editor-in-chief of the newly founded Journal of Graph Theory, asked William Tutte if he would contribute something for the first volume of the journal in connection with this announcement. Tutte responded with a short but pointed poem (employing his often-used pen-name Blanche Descartes) with the understated title Some Recent Progress in Combinatorics: Wolfgang Haken Smote the Kraken One! Two! Three! Four! Quoth he: “The monster is no more”. In the poem, Tutte likened the Four Color Problem to the legendary sea monster known as a kraken and proclaimed that Haken (along with Appel, of course) had slain this monster. With so many mistaken beliefs that the Four Color Theorem had been proved during the preceding century, it was probably not surprising that the announced