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