25proof by Appel and Haken was met with skepticism by many.While the proof wasreceived with enthusiasm by some, the reception was cool by others, even to thepoint of not being accepted by some that suchan argumentwas a proof at all.Itcertainly didn't help matters that copying, typographical, and technical errors werefound-even though corrected later.In1977,theyear following the announcementof the proof of the Four Color Theorem, Wolfgang Haken's son Armin, then agraduate student at the University of California at Berkeley, was asked to give atalk about the proof. He explained thatthe proof consisted of a rather short theoretical section, four hundredpages of detailed checklists showing that all relevant cases had been cov-ered, and about 1800 computer runs totaling over a thousand hours ofcomputer time.He went on to say that the audience seemed split into two groups, largely by ageand roughly at age 40. The older members of the audience questioned a proof thatmade such extensive use of computers, while the younger members questioned aproof that depended on hand-checking 400 pages of detail.The proof of the Four Color Theorem initiated a great number of philosophicaldiscussions as towhether such an argument was aproof and, in fact, what a proofis. Some believed that it was a requirement of a proof that it must be possiblefor a person to be able to read through the entire proof, even though it mightbe extraordinarily lengthy.Others argued that the nature of proof had changedover the years.Centuries ago a mathematician might have given a proof in aconversational style.Astime went on,proofshadbecomemorestructuredandwere concernedwiththewere presented in a very logicalmannWhilesomedistinctpossibilityof computercomputer-aidedproof.otherscounterederror1athis by saying that the literature is filled with incorrect proofs and misstatementssince human error is always a possibility, perhaps even more likely. Furthermore,many proofs written by modern mathematicians,even though not computer-aided,were so long that it is likely that few, if any,had read through these proofs with care.Also, those who shorten proofs by omitting arguments of some claims within a proofmay in fact be leaving out key elements of the proof, improving the opportunityfor human error.Then there are those who stated that knowing the Four ColorTheorem is true is not what is important.What is crucial is to know why only fourcolors are needed to color all maps. A computer-aided proof does not supply thisinformation.A second proof of the Four Color Theorem, using the same overall approachbut a different discharging procedure, a different unavoidable set of reducible con-figurations, and more powerful proofs of reducibility was announced and describedby Frank Allaire of Lakehead University, Canada in 1977, although the completedetails were never published.As Robin Thomas of the Georgia Institute of Technology reported, there ap-peared to be two major reasons for the lack of acceptance by some of the Appel-Haken proof: (1) part of the proof uses a computer and cannot be verified by hand;(2)thepartthatis supposedtobecheckedbyhandisso complicated thatno onemay have independently checked it at all.For these reasons, in 1996, Neil Robertson
25 proof by Appel and Haken was met with skepticism by many. While the proof was received with enthusiasm by some, the reception was cool by others, even to the point of not being accepted by some that such an argument was a proof at all. It certainly didn’t help matters that copying, typographical, and technical errors were found – even though corrected later. In 1977, the year following the announcement of the proof of the Four Color Theorem, Wolfgang Haken’s son Armin, then a graduate student at the University of California at Berkeley, was asked to give a talk about the proof. He explained that the proof consisted of a rather short theoretical section, four hundred pages of detailed checklists showing that all relevant cases had been covered, and about 1800 computer runs totaling over a thousand hours of computer time. He went on to say that the audience seemed split into two groups, largely by age and roughly at age 40. The older members of the audience questioned a proof that made such extensive use of computers, while the younger members questioned a proof that depended on hand-checking 400 pages of detail. The proof of the Four Color Theorem initiated a great number of philosophical discussions as to whether such an argument was a proof and, in fact, what a proof is. Some believed that it was a requirement of a proof that it must be possible for a person to be able to read through the entire proof, even though it might be extraordinarily lengthy. Others argued that the nature of proof had changed over the years. Centuries ago a mathematician might have given a proof in a conversational style. As time went on, proofs had become more structured and were presented in a very logical manner. While some were concerned with the distinct possibility of computer error in a computer-aided proof, others countered this by saying that the literature is filled with incorrect proofs and misstatements since human error is always a possibility, perhaps even more likely. Furthermore, many proofs written by modern mathematicians, even though not computer-aided, were so long that it is likely that few, if any, had read through these proofs with care. Also, those who shorten proofs by omitting arguments of some claims within a proof may in fact be leaving out key elements of the proof, improving the opportunity for human error. Then there are those who stated that knowing the Four Color Theorem is true is not what is important. What is crucial is to know why only four colors are needed to color all maps. A computer-aided proof does not supply this information. A second proof of the Four Color Theorem, using the same overall approach but a different discharging procedure, a different unavoidable set of reducible con- figurations, and more powerful proofs of reducibility was announced and described by Frank Allaire of Lakehead University, Canada in 1977, although the complete details were never published. As Robin Thomas of the Georgia Institute of Technology reported, there appeared to be two major reasons for the lack of acceptance by some of the AppelHaken proof: (1) part of the proof uses a computer and cannot be verified by hand; (2) the part that is supposed to be checked by hand is so complicated that no one may have independently checked it at all. For these reasons, in 1996, Neil Robertson
26CHAPTER0.THEORIGINOFGRAPHCOLORINGSDaniel P.Sanders,Paul Seymour,and Thomas constructed their own (computer-aided)proof of theFourColorTheorem.WhileAppel and Haken's unavoidable setof configurations consisted of 1482graphs, this newproof had an unavoidable set of633 graphs. In addition, while Appel and Haken used 487 discharging rules to con-struct their set of configurations, Robertson, Sanders, Seymour, and Thomas usedonly 32 discharging rules to construct their set of configurations. Thomas wrote:Appel and Haken's use of a computer 'may be a necessary evil', but thecomplication of the hand proof was more disturbing, particularly sincethe 4CT has a historyof incorrect“proofs"So in 1993,mainlyfor ourown peace of mind, we resolved to convince ourselves that the 4CT reallywastrue.The proof of the Four Color Theorem given by Robertson, Sanders, Seymour,and Thomas rested on the same idea as the Appel-Haken proof, however. Theseauthors proved that none of the 633 configurations can be contained in a minimumcounterexampletothe Four Color Theorem and so each of these configurations isreducible.As we noted, the Four Color Theorem could have been proved if any of thefollowing could be shown to be true.(1) Theregions of every map can be colored with four or fewer colors so thatneighboring regions are colored differently(2)The vertices of every planar graph can be colored with four or fewer colors sothat every two vertices joined by an edge are colored differently.(3) The edges of every cubic map can be colored with exactly three colors so thatevery three edges meeting at a vertex are colored differently.Coloring the regions, vertices, and edges of maps and planar graphs, inspiredby the desire to solve the Four Color Problem, has progressed far beyond this -tocoloring more general graphs and even to reinterpreting what is meant by coloring.It is the study of these topics into which we are about to venture
26 CHAPTER 0. THE ORIGIN OF GRAPH COLORINGS Daniel P. Sanders, Paul Seymour, and Thomas constructed their own (computeraided) proof of the Four Color Theorem. While Appel and Haken’s unavoidable set of configurations consisted of 1482 graphs, this new proof had an unavoidable set of 633 graphs. In addition, while Appel and Haken used 487 discharging rules to construct their set of configurations, Robertson, Sanders, Seymour, and Thomas used only 32 discharging rules to construct their set of configurations. Thomas wrote: Appel and Haken’s use of a computer ‘may be a necessary evil’, but the complication of the hand proof was more disturbing, particularly since the 4CT has a history of incorrect “proofs”. So in 1993, mainly for our own peace of mind, we resolved to convince ourselves that the 4CT really was true. The proof of the Four Color Theorem given by Robertson, Sanders, Seymour, and Thomas rested on the same idea as the Appel-Haken proof, however. These authors proved that none of the 633 configurations can be contained in a minimum counterexample to the Four Color Theorem and so each of these configurations is reducible. As we noted, the Four Color Theorem could have been proved if any of the following could be shown to be true. (1) The regions of every map can be colored with four or fewer colors so that neighboring regions are colored differently. (2) The vertices of every planar graph can be colored with four or fewer colors so that every two vertices joined by an edge are colored differently. (3) The edges of every cubic map can be colored with exactly three colors so that every three edges meeting at a vertex are colored differently. Coloring the regions, vertices, and edges of maps and planar graphs, inspired by the desire to solve the Four Color Problem, has progressed far beyond this – to coloring more general graphs and even to reinterpreting what is meant by coloring. It is the study of these topics into which we are about to venture
Chapter 1Introduction to GraphsIn the preceding chapter we were introduced to the famous map coloring problemknown astheFour ColorProblem.We sawthat thisproblem canalso be statedas a problem dealing with coloring the vertices of a certain class of graphs calledplanar graphs or as a problem dealing with coloring the edges of a certain subclass ofplanar graphs. This gives rise to coloring the vertices or coloring the edges of graphsin general. In order to provide the background needed to discuss this subject, wewill describe, over the next five chapters, some of the fundamental concepts andtheorems we will encounter in our investigation of graph colorings as well as somecommon terminology and notation in graph theory.1.1Fundamental TerminologyA graph G is a finite nonempty set V of objects called vertices (the singular isvertex) together with a set E of 2-element subsets of V called edges. Vertices aresometimes called points or nodes, while edges are sometimes referred to as linesor links. Each edge (u,u] of V is commonly denoted by uu or vu.If e=uv, thenthe edge e is said to join u and u. The number of vertices in a graph G is the orderof G and the number of edges is the size of G.We often use n for the order of agraph and m for its size. To indicate that a graph G has vertex set V and edgeset E.we sometimes write G =(VE).To emphasize that V is the vertex set of agraph G, we often write V as V(G). For the same reason, we also write E as E(G).A graph of order 1 is called a trivial graph and so a nontrivial graph has two ormore vertices. A graph of size 0 is an empty graph and so a nonempty graphhas one or more edges.Graphs are typically represented by diagrams in which each vertex is representedby a point or small circle (open or solid) and each edge is represented by a line seg-ment or curve joining the corresponding small circles. A diagram that represents agraph G is referred to as the graph G itself and the small circles and lines repre-senting the vertices and edges of G are themselves referred to as the vertices andedges of G.27
Chapter 1 Introduction to Graphs In the preceding chapter we were introduced to the famous map coloring problem known as the Four Color Problem. We saw that this problem can also be stated as a problem dealing with coloring the vertices of a certain class of graphs called planar graphs or as a problem dealing with coloring the edges of a certain subclass of planar graphs. This gives rise to coloring the vertices or coloring the edges of graphs in general. In order to provide the background needed to discuss this subject, we will describe, over the next five chapters, some of the fundamental concepts and theorems we will encounter in our investigation of graph colorings as well as some common terminology and notation in graph theory. 1.1 Fundamental Terminology A graph G is a finite nonempty set V of objects called vertices (the singular is vertex) together with a set E of 2-element subsets of V called edges. Vertices are sometimes called points or nodes, while edges are sometimes referred to as lines or links. Each edge {u, v} of V is commonly denoted by uv or vu. If e = uv, then the edge e is said to join u and v. The number of vertices in a graph G is the order of G and the number of edges is the size of G. We often use n for the order of a graph and m for its size. To indicate that a graph G has vertex set V and edge set E, we sometimes write G = (V, E). To emphasize that V is the vertex set of a graph G, we often write V as V (G). For the same reason, we also write E as E(G). A graph of order 1 is called a trivial graph and so a nontrivial graph has two or more vertices. A graph of size 0 is an empty graph and so a nonempty graph has one or more edges. Graphs are typically represented by diagrams in which each vertex is represented by a point or small circle (open or solid) and each edge is represented by a line segment or curve joining the corresponding small circles. A diagram that represents a graph G is referred to as the graph G itself and the small circles and lines representing the vertices and edges of G are themselves referred to as the vertices and edges of G. 27
28CHAPTER1.INTRODUCTIONTOGRAPHSFigure 1.1 shows a graph G with vertex set V = [t, u,u, w, , y,z] and edge setE =(tu, ty, uv, uw, w, y, wr, wz, yz]. Thus the order of this graph G is 7and its size is 9. In this drawing of G, the edges tu and uw intersect. This hasno significance. In particular, the point of intersection of these two edges is not avertex of G.G :OrwONyFigure 1.1: A graphIf uv is an edge of G, then u and v are adjacent vertices. Two adjacent verticesare referred to as neighbors of each other.The set of neighbors of a vertex uiscalled the open neighborhood of u (or simply the neighborhood of ) and isdenoted by N(u). The set N[u] = N(u) U [u) is called the closed neighborhoodof v. If uu and uw are distinct edges in G, then uu and vw are adjacent edges.The vertex u and the edge uu are said to be incident with each other. Similarly,w and u are incident.For the graph G of Figure 1.1, the vertices u and w are therefore adjacent in G,while the vertices u and are not adjacent. The edges uv and uw are adjacent inG, while the edges vy and wz are not adjacent. The vertex u is incident with theedge vw but is not incident with the edge wz.For nonempty disjoint sets A and B of vertices of G,we denote by [A, B] theset of edges of G joining a vertex of A and a vertex of B. For A = [u, u,y) andB = [w,z] in the graph G of Figure 1.1, [A,B] = (uw, w,yz].The degree of a vertex u in a graph G is the number of vertices in G thatare adjacent to v. Thus the degree of a vertex u is the number of the vertices inits neighborhood N(). Equivalently, the degree of uis the number of edges of Gincident with v.The degree of a vertex u is denoted by degc u or, more simply, bydeg u if the graph G under discussion is clear. A vertex of degree O is referred to asan isolated vertex and a vertex of degree 1 is an end-vertex or a leaf. An edgeincident with an end-vertex is called a pendant edge. The largest degree amongthe vertices of G is called the maximum degree of G is denoted by (G). Theminimum degree of G is denoted by (G).Thus if u is a vertex of a graph G oforder n,then0<s(G)≤degu≤△(G)≤n-1.For the graph G of Figure 1.1,deg = 1, deg t = deg z = 2, deg u = deg u = deg y = 3, and deg w = 4.Thus (G) = 1 and △(G) = 4
28 CHAPTER 1. INTRODUCTION TO GRAPHS Figure 1.1 shows a graph G with vertex set V = {t, u, v, w, x, y, z} and edge set E ={tu, ty, uv, uw, vw, vy, wx, wz, yz}. Thus the order of this graph G is 7 and its size is 9. In this drawing of G, the edges tu and vw intersect. This has no significance. In particular, the point of intersection of these two edges is not a vertex of G. . ......... ......... . ......... ......... . ......... ......... . ......... ......... . ......... ......... . ......... ......... . ........ ......... . . ..................................................................................... ..................................................................................... . . w x u t G : v y z Figure 1.1: A graph If uv is an edge of G, then u and v are adjacent vertices. Two adjacent vertices are referred to as neighbors of each other. The set of neighbors of a vertex v is called the open neighborhood of v (or simply the neighborhood of v) and is denoted by N(v). The set N[v] = N(v) ∪ {v} is called the closed neighborhood of v. If uv and vw are distinct edges in G, then uv and vw are adjacent edges. The vertex u and the edge uv are said to be incident with each other. Similarly, v and uv are incident. For the graph G of Figure 1.1, the vertices u and w are therefore adjacent in G, while the vertices u and x are not adjacent. The edges uv and uw are adjacent in G, while the edges vy and wz are not adjacent. The vertex v is incident with the edge vw but is not incident with the edge wz. For nonempty disjoint sets A and B of vertices of G, we denote by [A, B] the set of edges of G joining a vertex of A and a vertex of B. For A = {u, v, y} and B = {w, z} in the graph G of Figure 1.1, [A, B] = {uw, vw, yz}. The degree of a vertex v in a graph G is the number of vertices in G that are adjacent to v. Thus the degree of a vertex v is the number of the vertices in its neighborhood N(v). Equivalently, the degree of v is the number of edges of G incident with v. The degree of a vertex v is denoted by degG v or, more simply, by deg v if the graph G under discussion is clear. A vertex of degree 0 is referred to as an isolated vertex and a vertex of degree 1 is an end-vertex or a leaf. An edge incident with an end-vertex is called a pendant edge. The largest degree among the vertices of G is called the maximum degree of G is denoted by ∆(G). The minimum degree of G is denoted by δ(G). Thus if v is a vertex of a graph G of order n, then 0 ≤ δ(G) ≤ deg v ≤ ∆(G) ≤ n − 1. For the graph G of Figure 1.1, deg x = 1, deg t = deg z = 2, deg u = deg v = deg y = 3, and deg w = 4. Thus δ(G) = 1 and ∆(G) = 4
291.1.FUNDAMENTALTERMINOLOGYA well-known theorem in graph theory deals with the sum of the degrees of thevertices of a graph. This theorem was evidently first observed by the great Swissmathematician Leonhard Euler in a 1736 paper [68] that is now considered the firstpaper ever written on graph theory - even though graphs were never mentioned inthe paper. It is often referred to as the First Theorem of Graph Theory. (Somehave called this theorem the Handshaking Lemma, although Euler never usedthis name.)Theorem 1.1 (The First Theorem of Graph Theory)IfGisagraphofsizem,then deg u = 2m.VEV(G)Proof.When summing the degrees of the vertices of G, each edge of G is countedtwice, once for each of its two incident vertices.复The sum of the degrees of the vertices of the graph G of Figure 1.1 is 18, whichis twice the size 9 of G, as is guaranteed by Theorem 1.1.A vertex u in a graph G is even or odd, according to whether its degree in G iseven or odd.Thus the graph G of Figure 1.1 has three even vertices and four oddvertices. Whilea graph can have either an even or odd number of even verticesthis is not the case for odd vertices.Corollary 1.2Euery graph has an even number of odd ertices.Proof.Suppose that G is a graph of size m.By Theorem1.1, deg u= 2m,VEV(G)which is, of course, an even number. Since the sum of the degrees of the evenvertices of G is even,the sum of the degrees of the odd vertices of G must be even-as well, implying that G has an even number of odd vertices.A graph H is said to be a subgraph of a graph G if V(H) V(G) andE(H) C E(G). If V(H) = V(G), then H is a spanning subgraph of G. If H isa subgraph of a graph G and either V(H) is a proper subset of V(G) or E(H) isa proper subset of E(G), then H is a proper subgraph of G. For a nonemptysubset S of V(G), the subgraph G[Sl of G induced by S has S as its vertexset and two vertices u and u in S are adjacent in G[Sl if and only if u and u areadjacent in G. (The subgraph of G induced by S is also denoted by (S)G or simplyby (S) when the graph G is understood.) A subgraph H of a graph G is called aninduced subgraph if there is a nonempty subset S of V(G) such that H = G[S].Thus G[V(G)] =G. For a nonempty set X of edges of a graph G, the subgraphG[Xl induced by X has X as its edge set and a vertex belongs to G[Xl if u isincident with at least one edge in X. A subgraph H of G is edge-induced if thereis a nonempty subset X of E(G) such that H = G[X]. Thus G[E(G)] = G if andonly if Ghas no isolated vertices
1.1. FUNDAMENTAL TERMINOLOGY 29 A well-known theorem in graph theory deals with the sum of the degrees of the vertices of a graph. This theorem was evidently first observed by the great Swiss mathematician Leonhard Euler in a 1736 paper [68] that is now considered the first paper ever written on graph theory – even though graphs were never mentioned in the paper. It is often referred to as the First Theorem of Graph Theory. (Some have called this theorem the Handshaking Lemma, although Euler never used this name.) Theorem 1.1 (The First Theorem of Graph Theory) If G is a graph of size m, then X v∈V (G) deg v = 2m. Proof. When summing the degrees of the vertices of G, each edge of G is counted twice, once for each of its two incident vertices. The sum of the degrees of the vertices of the graph G of Figure 1.1 is 18, which is twice the size 9 of G, as is guaranteed by Theorem 1.1. A vertex v in a graph G is even or odd, according to whether its degree in G is even or odd. Thus the graph G of Figure 1.1 has three even vertices and four odd vertices. While a graph can have either an even or odd number of even vertices, this is not the case for odd vertices. Corollary 1.2 Every graph has an even number of odd vertices. Proof. Suppose that G is a graph of size m. By Theorem 1.1, X v∈V (G) deg v = 2m, which is, of course, an even number. Since the sum of the degrees of the even vertices of G is even, the sum of the degrees of the odd vertices of G must be even as well, implying that G has an even number of odd vertices. A graph H is said to be a subgraph of a graph G if V (H) ⊆ V (G) and E(H) ⊆ E(G). If V (H) = V (G), then H is a spanning subgraph of G. If H is a subgraph of a graph G and either V (H) is a proper subset of V (G) or E(H) is a proper subset of E(G), then H is a proper subgraph of G. For a nonempty subset S of V (G), the subgraph G[S] of G induced by S has S as its vertex set and two vertices u and v in S are adjacent in G[S] if and only if u and v are adjacent in G. (The subgraph of G induced by S is also denoted by hSiG or simply by hSi when the graph G is understood.) A subgraph H of a graph G is called an induced subgraph if there is a nonempty subset S of V (G) such that H = G[S]. Thus G[V (G)] = G. For a nonempty set X of edges of a graph G, the subgraph G[X] induced by X has X as its edge set and a vertex v belongs to G[X] if v is incident with at least one edge in X. A subgraph H of G is edge-induced if there is a nonempty subset X of E(G) such that H = G[X]. Thus G[E(G)] = G if and only if G has no isolated vertices