18.3 Path and Cycle Exchanges48318.2.4Let G bibicnlangraphwhichadmitsaHammilton doublecover (adouble cover by three Hamilton cycles).a) Show that each of these Hamilton cycles induces the same 4-face-colouring ofG (see Exercise 11.2.5)b) Fori≥l and 1≤j≤4, let piy be the number of faces of degreeiassignedcolour j. Show that r=1(i - 2)oij = (n -2)/2, 1 ≤ j ≤4 (and thus isindependent of the colour j)c) Deduce that no cubic planar bipartite graph on 0(mod4) vertices admits Hamilton doublecover(H.FETTER)d) Find an example of such a graph18.2.5a) Using the fact that the Petersen graph, drawn in Figure 18.12a, has no Hamil.ton cycle,showthatthlegraphinFigure18.12bhasnoHamiltoncyclethroughboth of the edges eandfb) The graph shown in Figure 18.12c is a redrawing of the one in Figure 18.12b.The Kelmans-Georges graph, depicted in Figure 18.10, is obtained from thePetersen graph of Figure 18.12a by substituting two copies of the graph ofFigure 18.12c for the two edges e and f. Deduce from (a) that this graph hasnoHamiltoncycle(A.K. KELMANS)佳(a) (b)Fig. 18.12. Kelmconstruction of the Kelmans-Georges graph18.3 Path and Cycle ExchangesIn this section, we describe how paths and cycles can be transformed into otherpaths and cycles by means of simple operations.These operations turn out to be
18.3 Path and Cycle Exchanges 483 ————— ————— 18.2.4 Let G be a cubic plane graph which admits a Hamilton double cover (a double cover by three Hamilton cycles). a) Show that each of these Hamilton cycles induces the same 4-face-colouring of G (see Exercise 11.2.5). b) For i ≥ 1 and 1 ≤ j ≤ 4, let φij be the number of faces of degree i assigned colour j. Show that n i=1(i − 2)φij = (n − 2)/2, 1 ≤ j ≤ 4 (and thus is independent of the colour j). c) Deduce that no cubic planar bipartite graph on 0(mod 4) vertices admits a Hamilton double cover. (H. Fetter) d) Find an example of such a graph. 18.2.5 a) Using the fact that the Petersen graph, drawn in Figure 18.12a, has no Hamilton cycle, show that the graph in Figure 18.12b has no Hamilton cycle through both of the edges e and f. b) The graph shown in Figure 18.12c is a redrawing of the one in Figure 18.12b. The Kelmans–Georges graph, depicted in Figure 18.10, is obtained from the Petersen graph of Figure 18.12a by substituting two copies of the graph of Figure 18.12c for the two edges e and f. Deduce from (a) that this graph has no Hamilton cycle. (A.K. Kelmans) (a) (b) (c) e e e f f f Fig. 18.12. Kelmans’ construction of the Kelmans–Georges graph 18.3 Path and Cycle Exchanges In this section, we describe how paths and cycles can be transformed into other paths and cycles by means of simple operations. These operations turn out to be
48418 Hamilton Cyclesvery helpful in searching for long paths and cycles (in particular, Hamilton pathsand cycles)First,alittlenotation.isavertexofapathPorcycleCwithaspecifedsense of traversal, we denote by y- and y+ the predecessor and successor of u,respectively, on P or C (provided that these vertices exist) (see Figure 18.13).uP(a)(b)Fig. 18.13. PrvcleCThis notation isidedtosubsetsSof V(P)orV(C)e would expect:S-:= [u-:wes] and s+:= [ut:we s]PATH EXCHANGESA natural way of searching for a Hamilton path in a graph is as follows. Let r bean arbitrary vertex. Suppose that an r-path aPy has already been found. If y isadjacent to a vertex z which does not lie on P, we can simply extend P by addingthe vertex z and the edge yz. On the other hand, if z is a neighbour of y on P,but notthe immediate predecessor of y.we can transform Pto an r-path Pi ofequallengthbyaddingtheedgeyzto(therebyfomingallipop,theumionofa path and a cycle having exactly one common vertex) and deleting the edge z2mation from P to P' is called a path erchange. Of(see Figure 18.14). This transforcourse, if it so happens that z+ is adjacent to a vertex not on P', the path P' canthen be extended to a path longer than P.PFig. 18.14. A path exchange
484 18 Hamilton Cycles very helpful in searching for long paths and cycles (in particular, Hamilton paths and cycles). First, a little notation. If v is a vertex of a path P or cycle C with a specified sense of traversal, we denote by v− and v+ the predecessor and successor of v, respectively, on P or C (provided that these vertices exist) (see Figure 18.13). (a) (b) v v v+ v+ v− v− P C Fig. 18.13. Predecessors and successors on a path P and a cycle C This notation is extended to subsets S of V (P) or V (C) as one would expect: S− := {v− : v ∈ S} and S+ := {v+ : v ∈ S} Path Exchanges A natural way of searching for a Hamilton path in a graph is as follows. Let x be an arbitrary vertex. Suppose that an x-path xPy has already been found. If y is adjacent to a vertex z which does not lie on P, we can simply extend P by adding the vertex z and the edge yz. On the other hand, if z is a neighbour of y on P, but not the immediate predecessor of y, we can transform P to an x-path P of equal length by adding the edge yz to P (thereby forming a lollipop, the union of a path and a cycle having exactly one common vertex) and deleting the edge zz+ (see Figure 18.14). This transformation from P to P is called a path exchange. Of course, if it so happens that z+ is adjacent to a vertex not on P , the path P can then be extended to a path longer than P. x z y x z z y + z+ P P Fig. 18.14. A path exchange
18.3PathandCycleExchanges485CYCLE EXCHANGESThere is also a simple way of transforming one cycle C into another cycle C' ofthe same length. If there are nonconsecutive vertices and y on C such that bothry and r+y+ are edges of the graph, the cycle C' obtained by adding these twoedges to C, and deleting the edges rr+and yy+ from C, is said to be derived fromC by means of a cycle erchange (seeFigure 18.15).CCytytyyFig.18.15.AcycleexchangeLet us remark in passing that cycle exchanges lead to an obvious heuristic forthe Travelling Salesman Problem (2.6).If C is a Hamilton cycle in a weightedgraph (G, w), andw(ry) +w(z+yt)<w(rr+)+w(yy+)then the cycle C'will be an improvement on C.Path and cycle exchanges are the key to establishing the existence of Hamiltonpaths and cycles in many classes of graphs.DIRAC'S THEOREMEvery complete graph on at least three vertices is evidently hamiltonian; indeed,the vertices of a Hamilton cycle can be selected one by one, in an arbitrary order.But suppose that our graph has considerably fewer edges. In particular, we mayask how large the minimum degree must be in order to guarantee the existence ofa Hamilton cycle.Thefollowing theorem of Dirac (1952b)answers this question.Theorem18.4DIRAC'sTHEOREMLet G be a simple graph of minimum degree , where ≥ n/2 and n ≥3. Then Gis hamiltonian.Proof Form a 2-edge-coloured complete graph K with vertex set V by colouringthe edges of G blue and the edges of its complement G red.Let C be a Hamiltoncycle of K with as many blue edges as possible. We show that every edge of C isblue,in other words,that CisaHamilton cycleof G
18.3 Path and Cycle Exchanges 485 Cycle Exchanges There is also a simple way of transforming one cycle C into another cycle C of the same length. If there are nonconsecutive vertices x and y on C such that both xy and x+y+ are edges of the graph, the cycle C obtained by adding these two edges to C, and deleting the edges xx+ and yy+ from C, is said to be derived from C by means of a cycle exchange (see Figure 18.15). x x y y x+ x+ y+ y+ C C Fig. 18.15. A cycle exchange Let us remark in passing that cycle exchanges lead to an obvious heuristic for the Travelling Salesman Problem (2.6). If C is a Hamilton cycle in a weighted graph (G,w), and w(xy) + w(x+y+) < w(xx+) + w(yy+) then the cycle C will be an improvement on C. Path and cycle exchanges are the key to establishing the existence of Hamilton paths and cycles in many classes of graphs. Dirac’s Theorem Every complete graph on at least three vertices is evidently hamiltonian; indeed, the vertices of a Hamilton cycle can be selected one by one, in an arbitrary order. But suppose that our graph has considerably fewer edges. In particular, we may ask how large the minimum degree must be in order to guarantee the existence of a Hamilton cycle. The following theorem of Dirac (1952b) answers this question. Theorem 18.4 Dirac’s Theorem Let G be a simple graph of minimum degree δ, where δ ≥ n/2 and n ≥ 3. Then G is hamiltonian. Proof Form a 2-edge-coloured complete graph K with vertex set V by colouring the edges of G blue and the edges of its complement G red. Let C be a Hamilton cycle of K with as many blue edges as possible. We show that every edge of C is blue, in other words, that C is a Hamilton cycle of G.
48618HamiltonCyclesSuppose not, and let r+ be a red edge of C, where + is the successor of r onC. If S := Nc() is the set of vertices joined to r by blue edges and T := Nc(r+)is the set of vertices joined to + by blue edges, then[S+I+T|=[S|+[T|=dc(r) +dG(r+)≥28≥nBecause a+ $ S+ and r+ $ T, we have S+UT c V I (r+), soIS+nT|=|S+/+[T|-S+UT|≥n-(n-1)=1Let y+ES+nT.Then theHamilton cycle C'obtained from C by exchanging theedges rr+ and yy+ for the blue edges ry and r+y+ has more blue edges than Ccontradicting the choice of C (seeFigure 18.15).Thus every edge of C is indeedblue.口Weremark that Theorem 18.4 can alsobeproved bymeans of path exchanges(Exercise 18.3.1).THECLOSUREOFAGRAPHObserve that theproof of Theorem18.4does not make full use of the hypothesisthat ≥n/2, but only of the weaker condition that the sum of the degrees of thetwo nonadjacent vertices and + is at least n.The same method of proof cantherefore be used to establish thefollowing lemma.Lemma 18.5 Let G be a simple graph and let u and be nonadjacent vertices inG whose degree sum is at least n.Then G is hamiltonian if and only if G+uu ishamiltonian.Proof If G is hamiltonian, so too is G+u.Conversely, suppose that G+uuhas aHamilton cycle C.Then, as in theproof of Theorem 18.4 (with :=u andr+ := u), there is a cycle exchange transforming C to a Hamilton cycle C' of G.口Lemma 18.5motivates thefollowing definition.The closure of a graph Gis thegraph obtained from G by recursively joining pairs of nonadjacent vertices whosedegree sum is at least n until no such pair remains. The order in which edges areadded toG in forming the closurehas no effect on the final result (Exercise18.3.2).口Lemma18.6 The closure of Gis well-defined.Figure 18.16 illustrates the formation of the closure G' of a graph G on sixvertices. In this example, it so happens that the closure is complete.The pertinenceof the closure operation to the study of Hamilton cycles resides in the followingobservation, due to Bondy and Chvatal (1976).Theorem 18.7 A simple graph is hamiltonian if and only if its closure is hamil.tonian
486 18 Hamilton Cycles Suppose not, and let xx+ be a red edge of C, where x+ is the successor of x on C. If S := NG(x) is the set of vertices joined to x by blue edges and T := NG(x+) is the set of vertices joined to x+ by blue edges, then |S+| + |T| = |S| + |T| = dG(x) + dG(x+) ≥ 2δ ≥ n Because x+ ∈/ S+ and x+ ∈/ T, we have S+ ∪ T ⊆ V \ {x+}, so |S+ ∩ T| = |S+| + |T|−|S+ ∪ T| ≥ n − (n − 1) = 1 Let y+ ∈ S+ ∩T. Then the Hamilton cycle C obtained from C by exchanging the edges xx+ and yy+ for the blue edges xy and x+y+ has more blue edges than C, contradicting the choice of C (see Figure 18.15). Thus every edge of C is indeed blue. We remark that Theorem 18.4 can also be proved by means of path exchanges (Exercise 18.3.1). The Closure of a Graph Observe that the proof of Theorem 18.4 does not make full use of the hypothesis that δ ≥ n/2, but only of the weaker condition that the sum of the degrees of the two nonadjacent vertices x and x+ is at least n. The same method of proof can therefore be used to establish the following lemma. Lemma 18.5 Let G be a simple graph and let u and v be nonadjacent vertices in G whose degree sum is at least n. Then G is hamiltonian if and only if G + uv is hamiltonian. Proof If G is hamiltonian, so too is G + uv. Conversely, suppose that G + uv has a Hamilton cycle C. Then, as in the proof of Theorem 18.4 (with x := u and x+ := v), there is a cycle exchange transforming C to a Hamilton cycle C of G. Lemma 18.5 motivates the following definition. The closure of a graph G is the graph obtained from G by recursively joining pairs of nonadjacent vertices whose degree sum is at least n until no such pair remains. The order in which edges are added to G in forming the closure has no effect on the final result (Exercise 18.3.2). Lemma 18.6 The closure of G is well-defined. Figure 18.16 illustrates the formation of the closure G of a graph G on six vertices. In this example, it so happens that the closure is complete. The pertinence of the closure operation to the study of Hamilton cycles resides in the following observation, due to Bondy and Chv´atal (1976). Theorem 18.7 A simple graph is hamiltonian if and only if its closure is hamiltonian.
48718.3PathandCycleExchangesGGFig.18.16.The closure of agraphProof Apply Lemma 18.5 each time an edge is added in the formation of the口closure.Theorem 18.7 has a number of interesting consequences. First, because allcomplete graphs on at least three vertices are evidently hamiltonian, we obtainthefollowing result.Corollary 18.8 Let G be a simple graph on at least three vertices whose closure口is complete.Then G is hamiltonian.Consider, for example, the graph of Figure 18.17.One readily checks that itsclosure is complete. By Corollary 18.8, this graph is therefore hamiltonian.It isperhaps interesting to note that the graph ofFigure18.17can be obtained from thegraph of Figure 18.2 by altering just one end of one edge, and yet we have results(Corollary 18.8 and Theorem 18.1) which tell us that this graph is hamiltonianwhereas the other is not.Fig.18.17.A graph whose closure is completeCorollary 18.8 can beused to derive various sufficient conditionsfor a graph tobe hamiltonian in terms of its vertex degrees. For example, because the closure isclearly complete when ≥ n/2, Dirac's Theorem (18.4) is an immediate corollary.Chvatal (1972) extended Dirac's Theorem to a wider class of graphs
18.3 Path and Cycle Exchanges 487 G G Fig. 18.16. The closure of a graph Proof Apply Lemma 18.5 each time an edge is added in the formation of the closure. Theorem 18.7 has a number of interesting consequences. First, because all complete graphs on at least three vertices are evidently hamiltonian, we obtain the following result. Corollary 18.8 Let G be a simple graph on at least three vertices whose closure is complete. Then G is hamiltonian. Consider, for example, the graph of Figure 18.17. One readily checks that its closure is complete. By Corollary 18.8, this graph is therefore hamiltonian. It is perhaps interesting to note that the graph of Figure 18.17 can be obtained from the graph of Figure 18.2 by altering just one end of one edge, and yet we have results (Corollary 18.8 and Theorem 18.1) which tell us that this graph is hamiltonian whereas the other is not. Fig. 18.17. A graph whose closure is complete Corollary 18.8 can be used to derive various sufficient conditions for a graph to be hamiltonian in terms of its vertex degrees. For example, because the closure is clearly complete when δ ≥ n/2, Dirac’s Theorem (18.4) is an immediate corollary. Chv´atal (1972) extended Dirac’s Theorem to a wider class of graphs