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