48818HamiltonCyclesTheorem 18.9 Let G be a simple graph with degree sequence (di,d2,...,dn)where di≤d2≤...≤dnandn≥3.Supposethat thereisno integerk<n/2such that d,≤k and dn-k< n -k. Then G is hamiltonian.Proof Let G' be the closure of G.We show that G' is complete.The conclusionthen follows from Corollary 18.8.We denote the degree of a vertex u in G'by d'(u).Assume, to the contrary, that G' is not complete, and let u and u be twononadjacentverticesin Gwith(18.7)d'(u)≤d'(u)and d'(u) + d'(u) as large as possible. Because no two nonadjacent vertices in G'can have degree sum n or more, we haved'(u)+d'(u)<n(18.8)Now denote by S the set of vertices in V \ (u) which are nonadjacent to yin G', and by T the set of vertices in V I (u] which are nonadjacent to u in G'.Clearly[S=n-1-d(u), and T=n-1-d(u)(18.9)Furthermore, by the choice of u and , each vertex of s has degree at most d'(u)and each vertex of TU (u) has degree at most d'(u). Setting k := d'(u) and using(18.8) and (18.9),we find that G'has at least k vertices of degree not exceeding kand at least n-k vertices of degree strictly less than n-k.Because G is a spanningsubgraph of G', the same is true of G; that is, dk≤k and dn-k < n -k.But thisis contrary to the hypothesis, because k < n/2 by (18.7) and (18.8). We concludethat the closure G'of G is indeed complete, and hence that G is hamiltonian, byCorollary18.8.口One can often deduce that a given graph is hamiltonian simply by computingits degree sequence and applying Theorem 18.9.This method works with thegraphof Figure 18.17, but not with thegraph G of Figure18.16, even though the closureof thelatter graph is complete.From these examples, we see thatTheorem 18.9 isstronger than Theorem 18.4 but not as strong as Corollary18.8.THE CHVATAL-ERDOS THEOREMWe conclude this section with a sufficient condition for hamiltonicity involving aremarkably simple relationship between the stability number and the connectivity,due to Chvatal and Erdos (1972).Its proof makes use of bridges, introduced inSection 10.4.TheOrem18.10THECHVATAL-ERDOsTHEOREMLet G be a graph on at least three vertices with stability numbera and connectivityK, wherea≤k.ThenG is hamiltonian
488 18 Hamilton Cycles Theorem 18.9 Let G be a simple graph with degree sequence (d1,d2,...,dn), where d1 ≤ d2 ≤ ··· ≤ dn and n ≥ 3. Suppose that there is no integer k < n/2 such that dk ≤ k and dn−k < n − k. Then G is hamiltonian. Proof Let G be the closure of G. We show that G is complete. The conclusion then follows from Corollary 18.8. We denote the degree of a vertex v in G by d (v). Assume, to the contrary, that G is not complete, and let u and v be two nonadjacent vertices in G with d (u) ≤ d (v) (18.7) and d (u) + d (v) as large as possible. Because no two nonadjacent vertices in G can have degree sum n or more, we have d (u) + d (v) < n (18.8) Now denote by S the set of vertices in V \ {v} which are nonadjacent to v in G , and by T the set of vertices in V \ {u} which are nonadjacent to u in G . Clearly |S| = n − 1 − d (v), and |T| = n − 1 − d (u) (18.9) Furthermore, by the choice of u and v, each vertex of S has degree at most d (u) and each vertex of T ∪ {u} has degree at most d (v). Setting k := d (u) and using (18.8) and (18.9), we find that G has at least k vertices of degree not exceeding k and at least n−k vertices of degree strictly less than n−k. Because G is a spanning subgraph of G , the same is true of G; that is, dk ≤ k and dn−k < n − k. But this is contrary to the hypothesis, because k < n/2 by (18.7) and (18.8). We conclude that the closure G of G is indeed complete, and hence that G is hamiltonian, by Corollary 18.8. One can often deduce that a given graph is hamiltonian simply by computing its degree sequence and applying Theorem 18.9. This method works with the graph of Figure 18.17, but not with the graph G of Figure 18.16, even though the closure of the latter graph is complete. From these examples, we see that Theorem 18.9 is stronger than Theorem 18.4 but not as strong as Corollary 18.8. The Chvatal–Erd ´ os Theorem ˝ We conclude this section with a sufficient condition for hamiltonicity involving a remarkably simple relationship between the stability number and the connectivity, due to Chv´atal and Erd˝os (1972). Its proof makes use of bridges, introduced in Section 10.4. Theorem 18.10 The Chvatal–Erd ´ os Theorem ˝ Let G be a graph on at least three vertices with stability number α and connectivity κ, where α ≤ κ. Then G is hamiltonian.
18.3PathandCycleExchanges489Proof Let C be a longest cycle in G. Suppose that C is not a Hamilton cycle. LetBbe a proper bridge of C in G,and denote by S its set of vertices of attachmentto C. For any two vertices r and y of S,there is a path rPy in B:this path isinternallydisjoint from C and of length at least two (seeFigure 18.18).BecauseC is a longest cycle, it follows that r and y are not consecutive vertices of CFor the same reason, + and y+ are nonadjacent; otherwise, the cycle obtainedby exchanging the edges rr+ and yyt of C for the path rPy and the edge r+y+would be longer than C. Thus S+ is a stable set of G, and is disjoint from S.2+rQBPOytyFig.18.18.Proof of theChvatal-ErdosTheorem (18.10)Let z be an internal vertex of B.Every neighbour of z on C belongs to S.Because S and S+ are disjoint, S+U[z) is a stable set. This implies that |S+|< αOn the other hand, S is a vertex cut of G because B-S is a component of G-S,so |S≥k.HenceK≤IS|=JS+I<QBut this contradicts the hypothesis. Therefore C is indeed a Hamilton cycle of G口Theorem 18.10 was generalized in a very nice way by Kouider (1994). A Hamil-ton cycle is a spanning cycle, that is, one which covers the entire vertex set of thegraph.Kouider proved that the vertex set of any 2-connected graph G can be cov-ered by a family of at most[α/| cycles.When α<k, this is just Theorem 18.10In Section 19.3, we discuss an analogous theorem for digraphs
18.3 Path and Cycle Exchanges 489 Proof Let C be a longest cycle in G. Suppose that C is not a Hamilton cycle. Let B be a proper bridge of C in G, and denote by S its set of vertices of attachment to C. For any two vertices x and y of S, there is a path xPy in B; this path is internally disjoint from C and of length at least two (see Figure 18.18). Because C is a longest cycle, it follows that x and y are not consecutive vertices of C. For the same reason, x+ and y+ are nonadjacent; otherwise, the cycle obtained by exchanging the edges xx+ and yy+ of C for the path xPy and the edge x+y+ would be longer than C. Thus S+ is a stable set of G, and is disjoint from S. x y x+ y+ B C P Fig. 18.18. Proof of the Chv´atal–Erd˝os Theorem (18.10) Let z be an internal vertex of B. Every neighbour of z on C belongs to S. Because S and S+ are disjoint, S+ ∪{z} is a stable set. This implies that |S+| < α. On the other hand, S is a vertex cut of G because B − S is a component of G− S, so |S| ≥ κ. Hence κ ≤ |S| = |S+| < α But this contradicts the hypothesis. Therefore C is indeed a Hamilton cycle of G. Theorem 18.10 was generalized in a very nice way by Kouider (1994). A Hamilton cycle is a spanning cycle, that is, one which covers the entire vertex set of the graph. Kouider proved that the vertex set of any 2-connected graph G can be covered by a family of at most α/κ cycles. When α ≤ κ, this is just Theorem 18.10. In Section 19.3, we discuss an analogous theorem for digraphs
49018HamiltonCyclesExercises18.3.1 Let Gbe a simple graph on at least three vertices in which the degree sumof any two nonadjacent vertices is at least n.Consider a vertex of G and anr-path P.a) Show that P can be transformed to aHamilton path Q of G,by means of pathextensions and path exchangesb)By considering the degree sum of the two ends of Q,deduce that G containsa Hamilton cycle.18.3.2ProveLemma18.6.18.3.3a)Let G bea nontrivial simple graph with degree sequence (di,d2,..,dn),wheredi<d2<...<dn.Supposethatthere isno integerk<(n+1)/2suchthatdk <k and dn-k+1 < n - k. Show that G is traceable.b)Deduce that every self-complementarygraph is traceable(C.R.J.CLAPHAM)18.3.4 Show that a simple graph and its complement cannot both satisfy thehypotheses of Theorem 18.9.(A.V.KOSTOCHKA AND D.B. WEST)18.3.5 Let G be a simple graph of minimum degree 8.Show that:a)Gcontainsapathof length28ifGisconnectedand≤(n-1)/2b)Gistraceableif≥ (n-1)/2.18.3.6 Let G be a graph with stability number α and connectivity K, where α≤K+1.ShowthatG istraceable.18.3.7 Let G be a simple graph, and let X be the set of vertices of G of degree atleast n/2.IfX|≥3, show that G has a cycle which includes X.(R. SHI)18.3.8 A graph G is degree-majorized by a graph H if v(G) = u(H) and thedegree sequence of G (in nondecreasing order) is majorized by that of H (seeExercise 12.2.5).a)Letmand nbepositiveintegerswithm<n/2andn≥3.Showthat thegraphKm V(Kn-2m+Km)is nonhamiltonian.b) Show that every nonhamiltonian simple graph on n vertices, where n ≥>3, isdegree-majorized byKmV (Kn-2m+Km)for somem<n/2.(V.CHVATAL)18.3.9 Let G := G[X, Y be a simple bipartite graph, where |X| = [Y| ≥ 2, withdegree sequence (di,d2,.,dn),where di ≤ d, ≤...≤ dn.Suppose that thereis no integer k≤ n/4 such that dk≤k and dn/2≤ n/2 -k.Show that G ishamiltonian
490 18 Hamilton Cycles Exercises 18.3.1 Let G be a simple graph on at least three vertices in which the degree sum of any two nonadjacent vertices is at least n. Consider a vertex x of G and an x-path P. a) Show that P can be transformed to a Hamilton path Q of G, by means of path extensions and path exchanges. b) By considering the degree sum of the two ends of Q, deduce that G contains a Hamilton cycle. 18.3.2 Prove Lemma 18.6. 18.3.3 a) Let G be a nontrivial simple graph with degree sequence (d1,d2,...,dn), where d1 ≤ d2 ≤ ... ≤ dn. Suppose that there is no integer k < (n + 1)/2 such that dk < k and dn−k+1 < n − k. Show that G is traceable. b) Deduce that every self-complementary graph is traceable. (C.R.J. Clapham) 18.3.4 Show that a simple graph and its complement cannot both satisfy the hypotheses of Theorem 18.9. (A.V. Kostochka and D.B. West) 18.3.5 Let G be a simple graph of minimum degree δ. Show that: a) G contains a path of length 2δ if G is connected and δ ≤ (n − 1)/2, b) G is traceable if δ ≥ (n − 1)/2. 18.3.6 Let G be a graph with stability number α and connectivity κ, where α ≤ κ + 1. Show that G is traceable. ————— ————— 18.3.7 Let G be a simple graph, and let X be the set of vertices of G of degree at least n/2. If |X| ≥ 3, show that G has a cycle which includes X. (R. Shi) 18.3.8 A graph G is degree-majorized by a graph H if v(G) = v(H) and the degree sequence of G (in nondecreasing order) is majorized by that of H (see Exercise 12.2.5). a) Let m and n be positive integers with m < n/2 and n ≥ 3. Show that the graph Km ∨ (Kn−2m + Km) is nonhamiltonian. b) Show that every nonhamiltonian simple graph on n vertices, where n ≥ 3, is degree-majorized by Km ∨ (Kn−2m + Km) for some m < n/2. (V. Chvatal) ´ 18.3.9 Let G := G[X,Y ] be a simple bipartite graph, where |X| = |Y | ≥ 2, with degree sequence (d1,d2,...,dn), where d1 ≤ d2 ≤ ··· ≤ dn. Suppose that there is no integer k ≤ n/4 such that dk ≤ k and dn/2 ≤ n/2 − k. Show that G is hamiltonian
49118.3Pathand CycleExchanges18.3.10a) Let G be a simple graph with m > ("-') +1 and n ≥ 3. Show that G ishamiltonian.(O.ORE)b) Show that the only nonhamiltonian simple graphs with n vertices and ("=')+1edges are thegraphs K, V (Kn-2+K) and, for n =5, the graph K2VK318.3.11a)Let Gbe aHamilton-connected graphwith n≥4.Show thatm≥3n/2b)Forall evenn≥4,constructaHamilton-connectedgraphGwithm=3n/2c) For all odd n ≥ 5, construct a Hamilton-connected graph G with m = (3n +1)/2.(J.W.MOON)18.3.12DeducefromTheorem18.10 thefollowing two results.a)LetGbeasimplegraphwithn>3inwhichthedegreesum of anytwononadjacent vertices is at least n. Then G is hamiltonian. (This is also a direct(O. ORE)consequenceof Corollary18.8.)b)Let G be a simplek-regular graph on 2k+1 vertices, wherek ≥2.Then G ishamiltonian.(C.ST.J.A. NASH-WILLIAMS)18.3.13Avertexyis insertable intoapathPif w isadjacent totwoconsecutivevertices z,z+ of P.Let rPy and uQube disjoint paths.The path Q is absorbableinto P if there is a path with vertex set V(P) UV(Q). Suppose that each vertexof Qis insertableintoP.ShowthatQis absorbableintoP.(A.AINOUCHE)18.3.14 Let G be a connected graph which contains a path of length k, and inwhich every such path is contained in a cycle of length at least l.a) Show that each path in G of length less than k is contained in a path of lengthk.b) Deduce that each path in G of length less than k is contained in a cycle oflength at least l.(T.D.PARSONS)18.3.15a)Let Gbe a simple 2-connected graph, and let rPy be a longest path in G.Fora vine (r;Qiyi:1 ≤ i≤r) on P, consider the cycles C, := P, UQi+whereP,:= ,Pyi, 1<i≤ r, and the cycle C := A-,C,. Suppose the vine chosenso that:r is as small as possible.subject to this condition, V(C)nV(P)/is as large as possible.Show that:i) (r)U (y) UN(r)UN(y) C V(C),ii) C is either a Hamilton cycle of G or a cycle of length at least d(r)+d(y)b)Deduce thefollowing statements.i) If G is a simple 2-connected graph with ≤ n/2, then G contains a cycleof length at least 25.(G.A.DIRAC)
18.3 Path and Cycle Exchanges 491 18.3.10 a) Let G be a simple graph with m > n−1 2 + 1 and n ≥ 3. Show that G is hamiltonian. (O. Ore) b) Show that the only nonhamiltonian simple graphs with n vertices and n−1 2 +1 edges are the graphs K1 ∨ (Kn−2 + K1) and, for n = 5, the graph K2 ∨ K3. 18.3.11 a) Let G be a Hamilton-connected graph with n ≥ 4. Show that m ≥ 3n/2. b) For all even n ≥ 4, construct a Hamilton-connected graph G with m = 3n/2. c) For all odd n ≥ 5, construct a Hamilton-connected graph G with m = (3n + 1)/2. (J.W. Moon) 18.3.12 Deduce from Theorem 18.10 the following two results. a) Let G be a simple graph with n ≥ 3 in which the degree sum of any two nonadjacent vertices is at least n. Then G is hamiltonian. (This is also a direct consequence of Corollary 18.8.) (O. Ore) b) Let G be a simple k-regular graph on 2k + 1 vertices, where k ≥ 2. Then G is hamiltonian. (C.St.J.A. Nash-Williams) 18.3.13 A vertex v is insertable into a path P if v is adjacent to two consecutive vertices z,z+ of P. Let xPy and uQv be disjoint paths. The path Q is absorbable into P if there is a path with vertex set V (P) ∪ V (Q). Suppose that each vertex of Q is insertable into P. Show that Q is absorbable into P. (A. Ainouche) 18.3.14 Let G be a connected graph which contains a path of length k, and in which every such path is contained in a cycle of length at least l. a) Show that each path in G of length less than k is contained in a path of length k. b) Deduce that each path in G of length less than k is contained in a cycle of length at least l. (T.D. Parsons) 18.3.15 a) Let G be a simple 2-connected graph, and let xPy be a longest path in G. For a vine (xiQiyi : 1 ≤ i ≤ r) on P, consider the cycles Ci := Pi ∪ Qi, where Pi := xiPyi, 1 ≤ i ≤ r, and the cycle C := r i=1Ci. Suppose the vine chosen so that: r is as small as possible, subject to this condition, |V (C) ∩ V (P)| is as large as possible. Show that: i) {x}∪{y} ∪ N(x) ∪ N(y) ⊆ V (C), ii) C is either a Hamilton cycle of G or a cycle of length at least d(x) + d(y). b) Deduce the following statements. i) If G is a simple 2-connected graph with δ ≤ n/2, then G contains a cycle of length at least 2δ. (G.A. Dirac)
49218 Hamilton Cyclesii) If G := G(r, y) is a simple 2-connected graph such that d(u) ≥ k for allu+ a,y, then G contains an ry-path of length at least k.(P.ERDOs AND T.GALLAI)18.3.16 Let G be a claw-free graph.a) Show that the subgraph of G induced by the neighbours of any vertex is eitherconnected(Type1)orhasexactlytwocomponents,bothofwhicharecomplete(Type 2).b) Let u be a vertex of Type 1 in G whose neighbourhood is not a clique, andlet G'be a graph obtained from G by adding an edge joining two nonadjacentneighbours of u.Show that G' is hamiltonian if and only if G is hamiltonianc) The Ryjacek closure of G is the graph H obtained by recursively applying theoperation described in (b) until the neighbourhood of every vertex of Type1is a clique. Showthat:i) H is the line graph of a triangle-free graph,(Z.RYJACEK)ii)H is hamiltonian if and onlyif G is hamiltonian.18.4PathExchangesandParityIn theprevious section,we saw that a simplegraph each vertex ofwhich isadjacentto more than half of the other vertices contains a Hamilton cycle. More surprisingperhaps, is the fact that one can say something about Hamilton cycles in cubicgraphs. Such graphs need not have any Hamilton cycles at all (the Petersen andCoxeter graphs being two familiar examples).However,as C.A.B.Smithproved.each edge of a cubic graph lies in an even number of Hamilton cycles (see Tutte(1946). From this one can deduce that if a cubic graph has one Hamilton cycle,it has at least three of them (Exercise 18.4.la).Smith's Theorem was extendedbyThomason(1978)using the exchange operation betweenr-paths introduced inSection 18.1. We now describe his idea.THELOLLIPOPLEMMALet G be a graph (not necessarily simple). The -path graph of G is the graphwhose vertices are the longest r-paths of G, two such paths being adjacent if andonly if they arerelated by a path exchange (see Figure 18.19).Thomason (1978)made use of this concept to establish a basic property of r-paths.Theorem18.11THELOLLIPOPLEMMALet G be a connected graph on at least two vertices, and let be a verter of GThen the number of longest r-paths of G that terminate in a verter of even degreeis even.Proof Let H denote the -path graph of G and let P be a longest r-path of G.If P terminates in y
492 18 Hamilton Cycles ii) If G := G(x,y) is a simple 2-connected graph such that d(v) ≥ k for all v = x,y, then G contains an xy-path of length at least k. (P. Erdos and T. Gallai) ˝ 18.3.16 Let G be a claw-free graph. a) Show that the subgraph of G induced by the neighbours of any vertex is either connected (Type 1) or has exactly two components, both of which are complete (Type 2). b) Let v be a vertex of Type 1 in G whose neighbourhood is not a clique, and let G be a graph obtained from G by adding an edge joining two nonadjacent neighbours of v. Show that G is hamiltonian if and only if G is hamiltonian. c) The Ryj´aˇcek closure of G is the graph H obtained by recursively applying the operation described in (b) until the neighbourhood of every vertex of Type 1 is a clique. Show that: i) H is the line graph of a triangle-free graph, ii) H is hamiltonian if and only if G is hamiltonian. (Z. Ryja´cek) ˇ 18.4 Path Exchanges and Parity In the previous section, we saw that a simple graph each vertex of which is adjacent to more than half of the other vertices contains a Hamilton cycle. More surprising, perhaps, is the fact that one can say something about Hamilton cycles in cubic graphs. Such graphs need not have any Hamilton cycles at all (the Petersen and Coxeter graphs being two familiar examples). However, as C. A. B. Smith proved, each edge of a cubic graph lies in an even number of Hamilton cycles (see Tutte (1946)). From this one can deduce that if a cubic graph has one Hamilton cycle, it has at least three of them (Exercise 18.4.1a). Smith’s Theorem was extended by Thomason (1978) using the exchange operation between x-paths introduced in Section 18.1. We now describe his idea. The Lollipop Lemma Let G be a graph (not necessarily simple). The x-path graph of G is the graph whose vertices are the longest x-paths of G, two such paths being adjacent if and only if they are related by a path exchange (see Figure 18.19). Thomason (1978) made use of this concept to establish a basic property of x-paths. Theorem 18.11 The Lollipop Lemma Let G be a connected graph on at least two vertices, and let x be a vertex of G. Then the number of longest x-paths of G that terminate in a vertex of even degree is even. Proof Let H denote the x-path graph of G and let P be a longest x-path of G. If P terminates in y,