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 announced24 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