18.4Path Exchanges andParity493acbadredabredbarcbdarbcdarbaderadcbrabcdrabderadbcG(a)(b)Fig.18.19. (a)Agraph G, (b) ther-pathgraph of GdH(P)=dc(y)-1Thus y is of even degree in G if and only if P is of odd degree in H. Because thenumber of vertices of odd degree in H is even by Corollary 1.2, the number of口longest r-paths in G that terminate in a vertex of even degree is also even.Corollary18.12LetGbeagraphonat leastthreevertices,and letandybetwo vertices of G.Suppose that each verter of G other than r and y is of odddegree.Then the number of Hamilton ry-paths in G is even.In particular, if G isa graph in which all vertices are of odd degree, then each edge of G lies in an evennumber ofHamiltoncycles.Proof We may assume that G has at least one Hamilton ry-path, otherwise theconclusion is trivial. Set G' := G-y.The longest r-paths of G' are Hamiltonpaths of G', and each Hamilton ry-path of G is an extension of such a path. LetrP'zbe a Hamilton path of G'.If zis of odd degree in G, the number of edgesbetween y and z is even, because z is of odd degree in G.Thus P' gives rise toan even number of Hamilton ry-paths of G in this case.On the otherhand, if zis of even degree in G', then P'gives rise to an odd number of Hamilton ry-pathsof G.But,byTheorem18.11,thenumber ofHamilton r-paths ofGending inavertex of even degree is even. Hence the total number of Hamilton ry-paths in G口is even.A special case of Corollary 18.12 is the theorem of C.A.B.Smith referred toearlier.Theorem18.13SMITH'sTHEOREM口In any cubic graph, each edge lies in an even number of Hamilton cycles.The results of this section give rise to intriguing algorithmic questions. Smith'sTheorem implies that every cubic graph with one Hamilton cycle has a secondHamilton cycle.Chrobak and Poljak (1988)asked how hard it is to find a secondHamilton cycle in such a graph when supplied with one of them. The answer isunknown.In particular,no polynomial-timealgorithm has been devised for solvingthis problem
18.4 Path Exchanges and Parity 493 x a b c d G xadbc xadcb xabcd xabdc xbcda xbadc xcbda xcbad xcdab xcdba (a) (b) Fig. 18.19. (a) A graph G, (b) the x-path graph of G dH(P) = dG(y) − 1 Thus y is of even degree in G if and only if P is of odd degree in H. Because the number of vertices of odd degree in H is even by Corollary 1.2, the number of longest x-paths in G that terminate in a vertex of even degree is also even. Corollary 18.12 Let G be a graph on at least three vertices, and let x and y be two vertices of G. Suppose that each vertex of G other than x and y is of odd degree. Then the number of Hamilton xy-paths in G is even. In particular, if G is a graph in which all vertices are of odd degree, then each edge of G lies in an even number of Hamilton cycles. Proof We may assume that G has at least one Hamilton xy-path, otherwise the conclusion is trivial. Set G := G − y. The longest x-paths of G are Hamilton paths of G , and each Hamilton xy-path of G is an extension of such a path. Let xP z be a Hamilton path of G . If z is of odd degree in G , the number of edges between y and z is even, because z is of odd degree in G. Thus P gives rise to an even number of Hamilton xy-paths of G in this case. On the other hand, if z is of even degree in G , then P gives rise to an odd number of Hamilton xy-paths of G. But, by Theorem 18.11, the number of Hamilton x-paths of G ending in a vertex of even degree is even. Hence the total number of Hamilton xy-paths in G is even. A special case of Corollary 18.12 is the theorem of C. A. B. Smith referred to earlier. Theorem 18.13 Smith’s Theorem In any cubic graph, each edge lies in an even number of Hamilton cycles. The results of this section give rise to intriguing algorithmic questions. Smith’s Theorem implies that every cubic graph with one Hamilton cycle has a second Hamilton cycle. Chrobak and Poljak (1988) asked how hard it is to find a second Hamilton cycle in such a graph when supplied with one of them. The answer is unknown. In particular, no polynomial-time algorithm has been devised for solving this problem.
49418HamiltonCyclesUNIQUELYHAMILTONIANGRAPHSAgraph is called uniquelyhamiltonian if ithas exactlyoneHamilton cycle.Corollary 18.12 implies that no regular graph of odd degree is uniquely hamiltonianSheehan (1975) conjectured that the same is true of regular simple graphs of evendegree four or more.Sheehan's Conjecture can be restricted without loss of generality to 4-regulargraphs, as stated below.For if C is a Hamilton cycle of G,then the spanningsubgraph G /E(C) is regular of positive even degree, and hence has a 2-factor F(Exercise 16.4.16b). The graph H := FUC is a 4-regular spanning subgraph withaHamilton cycle C.If we could prove that H had a second Hamilton cycle, thenGwould alsohavethis secondHamilton cycle.SHEEHAN'S CONJECTUREConjecture18.14Eueryhamiltonian4-regularsimplegraphhas at leasttwoHamilton cycles.Note that the conditions of simplicity and regularity here are essential. Examples of uniquely hamiltonian 4-regular graphs with multiple edges and of uniquelyhamiltonian simplegraphs ofminimum degreefour were constructed by Fleischner(1994,2007)By applying the methods described in this chapter, Thomassen (1998) obtaineda general sufficient condition for the existence of at least two Hamilton cycles in ahamiltonian graph. Thomassen's argument is based on thefollowing concepts.Consider a (not necessarily proper) 2-edge-colouring of a graph G in red andblue. A set S of vertices of G is called red-stable if no two vertices of S are joinedby a red edge, and blue-dominating if every vertex of VIS is adjacent by a blueedgetoatleastonevertexofS.Theorem 18.15 Let G be a graph and let C be a Hamilton cycle of G. Colour theedges of C red and the remaining edges of G blue.Suppose that there is a red-stableblue-dominating set S in G.Then G has a second Hamilton cycle.Proof Let S be a red-stable blue-dominating set, and let T := S-US+. Considerthe spanning subgraph H of G the edge set of which consists of all red edges and,for each vertex y e T, one blue edge joining y to a vertex of S. In H, each vertexof T has degree three, whereas every other vertex of VS has degree two.BecauseS is red-stable,itfollowsthatH-ShasexactlyScomponents,each ofwhich isa path whose ends are in T.By Theorem 18.1, everyHamilton cycle of H includesall of these paths. Let e = ry E E(C),where r e S and y E T.By Theorem 18.1l,the number of longest r-paths of H e that terminate in a vertex of even degreeis even.But the Hamilton path C e is one such path, because y has degree two
494 18 Hamilton Cycles Uniquely Hamiltonian Graphs A graph is called uniquely hamiltonian if it has exactly one Hamilton cycle. Corollary 18.12 implies that no regular graph of odd degree is uniquely hamiltonian. Sheehan (1975) conjectured that the same is true of regular simple graphs of even degree four or more. Sheehan’s Conjecture can be restricted without loss of generality to 4-regular graphs, as stated below. For if C is a Hamilton cycle of G, then the spanning subgraph G \ E(C) is regular of positive even degree, and hence has a 2-factor F (Exercise 16.4.16b). The graph H := F ∪ C is a 4-regular spanning subgraph with a Hamilton cycle C. If we could prove that H had a second Hamilton cycle, then G would also have this second Hamilton cycle. Sheehan’s Conjecture Conjecture 18.14 Every hamiltonian 4-regular simple graph has at least two Hamilton cycles. Note that the conditions of simplicity and regularity here are essential. Examples of uniquely hamiltonian 4-regular graphs with multiple edges and of uniquely hamiltonian simple graphs of minimum degree four were constructed by Fleischner (1994, 2007). By applying the methods described in this chapter, Thomassen (1998) obtained a general sufficient condition for the existence of at least two Hamilton cycles in a hamiltonian graph. Thomassen’s argument is based on the following concepts. Consider a (not necessarily proper) 2-edge-colouring of a graph G in red and blue. A set S of vertices of G is called red-stable if no two vertices of S are joined by a red edge, and blue-dominating if every vertex of V \ S is adjacent by a blue edge to at least one vertex of S. Theorem 18.15 Let G be a graph and let C be a Hamilton cycle of G. Colour the edges of C red and the remaining edges of G blue. Suppose that there is a red-stable blue-dominating set S in G. Then G has a second Hamilton cycle. Proof Let S be a red-stable blue-dominating set, and let T := S− ∪S+. Consider the spanning subgraph H of G the edge set of which consists of all red edges and, for each vertex y ∈ T, one blue edge joining y to a vertex of S. In H, each vertex of T has degree three, whereas every other vertex of V \S has degree two. Because S is red-stable, it follows that H − S has exactly |S| components, each of which is a path whose ends are in T. By Theorem 18.1, every Hamilton cycle of H includes all of these paths. Let e = xy ∈ E(C), where x ∈ S and y ∈ T. By Theorem 18.11, the number of longest x-paths of H \ e that terminate in a vertex of even degree is even. But the Hamilton path C \ e is one such path, because y has degree two
18.4Path Exchanges and Parity495in H e.Let P be another such path.Then P+e is a second Hamilton cycle of口H, hence also of G.One easy consequence of Theorem 18.15 is the following result for bipartitegraphs.Corollary18.16 Let G[X,Y]be a simple hamiltonian bipartitegraph in whicheach verter of Y has degree three or more. Then G has at least two Hamiltoncycles.Proof Let C be a Hamilton cycle of G.Colour the edges of C red and theremaining edges of G blue.Each vertex of Y is then incident to at least one blueedge, so X is a red-stable blue-dominating set in G. By Theorem 18.15, G has a口second Hamilton cycle.Thomassen (1998)applied theLocal Lemma (Theorem 13.12)to showthat ifk is sufficiently large, then every simple hamiltonian k-regular graph fulfills therequirements of Theorem 18.15 and hence has at least two Hamilton cycles.Theorem18.17Fork≥73,everysimplehamiltonian k-regular graphhas atleast two Hamilton cycles.Proof Let G be a simple hamiltonian k-regular graph, and let C be a Hamiltoncycle of G. As in Theorem 18.15, we colour the edges of C red and the remainingedges of Gblue.We now select eachvertex of G independently, each with proba-bility p, so as to obtain a random subset S of V.We show that,for an appropriatechoice of p, this set S is, with positive probability,a red-stable blue-dominatingset.The theorem then follows on applying Theorem 18.15.For each element of E(C) UV(G), we define a‘bad'event, as follows.Ae:bothendsof edgeeof CbelongtoS.DDB: neither verter u of G nor any verter joined to by a blue edge belongs toS.We have p(Ae) = p2 and P(B) = (1 - p)*-1, because each vertex hasblue degree k -2. We define a dependency graph H for these events, with vertexset E(C)U V(G),by declaring two vertices to be adjacent in H if the sets ofvertices involved in the corresponding events intersect. The vertices involved inAe, namely the two ends of e, are each involved in one other event Ay and k -1events Bu. Thus e has degree at most 2 + (2k - 2) in the dependency graph H.The k -1 vertices involved in Bu are each involved in two events Ae, and aretogether involved in a total of at most (k-2)2 other events Bw.Thus has degreeat most (2k -- 2) + (k - 2)? in H. In order to apply the Local Lemma, we musttherefore select a value for p and numbers (associated with each event Ae) andy(associated witheach event Bu)such that:P’≤a(1 - a) (1 - g)2k-2 and (1 - p)-1 ≤y(1 - a)2k-2(1 - )(-2)2We may simplify these expressions by setting := a? and y := bk-1:
18.4 Path Exchanges and Parity 495 in H \ e. Let P be another such path. Then P + e is a second Hamilton cycle of H, hence also of G. One easy consequence of Theorem 18.15 is the following result for bipartite graphs. Corollary 18.16 Let G[X,Y ] be a simple hamiltonian bipartite graph in which each vertex of Y has degree three or more. Then G has at least two Hamilton cycles. Proof Let C be a Hamilton cycle of G. Colour the edges of C red and the remaining edges of G blue. Each vertex of Y is then incident to at least one blue edge, so X is a red-stable blue-dominating set in G. By Theorem 18.15, G has a second Hamilton cycle. Thomassen (1998) applied the Local Lemma (Theorem 13.12) to show that if k is sufficiently large, then every simple hamiltonian k-regular graph fulfills the requirements of Theorem 18.15 and hence has at least two Hamilton cycles. Theorem 18.17 For k ≥ 73, every simple hamiltonian k-regular graph has at least two Hamilton cycles. Proof Let G be a simple hamiltonian k-regular graph, and let C be a Hamilton cycle of G. As in Theorem 18.15, we colour the edges of C red and the remaining edges of G blue. We now select each vertex of G independently, each with probability p, so as to obtain a random subset S of V . We show that, for an appropriate choice of p, this set S is, with positive probability, a red-stable blue-dominating set. The theorem then follows on applying Theorem 18.15. For each element of E(C) ∪ V (G), we define a ‘bad’ event, as follows. Ae: both ends of edge e of C belong to S. Bv: neither vertex v of G nor any vertex joined to v by a blue edge belongs to S. We have p(Ae) = p2 and P(Bv) = (1 − p)k−1, because each vertex v has blue degree k − 2. We define a dependency graph H for these events, with vertex set E(C) ∪ V (G), by declaring two vertices to be adjacent in H if the sets of vertices involved in the corresponding events intersect. The vertices involved in Ae, namely the two ends of e, are each involved in one other event Af and k − 1 events Bv. Thus e has degree at most 2 + (2k − 2) in the dependency graph H. The k − 1 vertices involved in Bv are each involved in two events Ae, and are together involved in a total of at most (k −2)2 other events Bw. Thus v has degree at most (2k − 2) + (k − 2)2 in H. In order to apply the Local Lemma, we must therefore select a value for p and numbers x (associated with each event Ae) and y (associated with each event Bv) such that: p2 ≤ x(1 − x) 2(1 − y) 2k−2 and (1 − p) k−1 ≤ y(1 − x) 2k−2(1 − y) (k−2)2 We may simplify these expressions by setting x := a2 and y := bk−1:
49618HamiltonCyclesp≤a(1-a2)(1-6k-1)k-1 and 1-p≤b(1-a2)2(1-bk-1)k=3Thus1 ≤ a(1 - a2)(1 - bk-1)k-1 + b(1 - a2)2(1 - bk-1)±-3Fork≥73,a solution to this inequality is obtained by settinga=.25and b=.89口resulting in a value of .2305 for p.Thebound k≥73 inTheorem18.17was reduced tok≥23byHaxell etal.(2007).However, Sheehan's Conjectureremains open.To conclude this discussion of Sheehan's Conjecture, let us notea more recentconjecture, due to Fleischner (2007), which bears a close resemblance to it.Conjecture18.18FLEISCHNER'sCONJECTUREEvery hamiltonian 4-connected graph has at least two Hamilton cycles.This conjecture holds for planargraphs (see Section 18.6).Exercises18.4.1a) Showthat:i) every hamiltonian cubic graph has at least three Hamilton cycles.i) both the complete graph Ky and the generalized Petersen graph P2.g haveexactly three Hamilton cycles.b) For each integer n ≥ 2, construct a simple cubic graph on 2n vertices withexactly threeHamilton cycles.18.4.2 Let G be a cubic hamiltonian graph and let e be an edge of G. Form abipartite graph H[C, F], where C is the set of proper 3-edge colourings of G andF is the set of even 2-factors of G (that is, 2-factors all components of which areeven cycles)that include the edge e, with c EC joined to F EF if and only if Fis induced by the union of two of the colours in the 3-edge-colouring c.a) Show that:i) every vertex in C has degree two.ii)avertexF Fwithk components has degree 2k-1b) Deduce Smith's Theorem (18.13).18.4.3 Consider the graph G of Figure 18.20.a) Show that:i) the edge e lies in no Hamilton cycle and no Hamilton ry-path of Gii) G has exactly one Hamilton cycle and exactly one Hamilton Ty-path.b)Deducethat:i) the graph G + ry, in which one vertex is of degree four and the rest are ofdegree three, has exactlytwo Hamilton cycles
496 18 Hamilton Cycles p ≤ a(1 − a2)(1 − bk−1) k−1 and 1 − p ≤ b(1 − a2) 2(1 − bk−1) k−3 Thus 1 ≤ a(1 − a2)(1 − bk−1) k−1 + b(1 − a2) 2(1 − bk−1) k−3 For k ≥ 73, a solution to this inequality is obtained by setting a = .25 and b = .89, resulting in a value of .2305 for p. The bound k ≥ 73 in Theorem 18.17 was reduced to k ≥ 23 by Haxell et al. (2007). However, Sheehan’s Conjecture remains open. To conclude this discussion of Sheehan’s Conjecture, let us note a more recent conjecture, due to Fleischner (2007), which bears a close resemblance to it. Conjecture 18.18 Fleischner’s Conjecture Every hamiltonian 4-connected graph has at least two Hamilton cycles. This conjecture holds for planar graphs (see Section 18.6). Exercises 18.4.1 a) Show that: i) every hamiltonian cubic graph has at least three Hamilton cycles, ii) both the complete graph K4 and the generalized Petersen graph P2,9 have exactly three Hamilton cycles. b) For each integer n ≥ 2, construct a simple cubic graph on 2n vertices with exactly three Hamilton cycles. 18.4.2 Let G be a cubic hamiltonian graph and let e be an edge of G. Form a bipartite graph H[C, F], where C is the set of proper 3-edge colourings of G and F is the set of even 2-factors of G (that is, 2-factors all components of which are even cycles) that include the edge e, with c ∈ C joined to F ∈ F if and only if F is induced by the union of two of the colours in the 3-edge-colouring c. a) Show that: i) every vertex in C has degree two, ii) a vertex F ∈ F with k components has degree 2k−1. b) Deduce Smith’s Theorem (18.13). 18.4.3 Consider the graph G of Figure 18.20. a) Show that: i) the edge e lies in no Hamilton cycle and no Hamilton xy-path of G, ii) G has exactly one Hamilton cycle and exactly one Hamilton xy-path. b) Deduce that: i) the graph G + xy, in which one vertex is of degree four and the rest are of degree three, has exactly two Hamilton cycles
18.4Path Exchanges and Parity497ii) the graph H of Figure 18.20, in which two vertices are of degree four andthe rest are of degree three, has a unique Hamilton cycle.(R.C.ENTRINGERANDH.SWART)UGHFig.18.20.Construction of a uniquely hamiltonian almost cubic graph718.4.4 Show that every cubic bipartite graph on at least four vertices has an even(A.KOTZIG)numberof Hamilton cycles.18.4.5a)Let G be a simple cubic graph.Show that the linegraph of G admits a Hamiltondecomposition if and only if G is 3-edge-colourable.(A.KOTZIG)b)Deduce that the line graph of the Petersen graph is a 4-connected 4-regulargraph which admits no Hamilton decomposition.18.4.6a) Let G be a 4-regular plane graph that admits a decomposition into two Hamil-ton cycles, C and D.DenotebyFi1,Fi2,F21, and F22 the sets of faces ofGinteriortobothC and D,interiorto C butexterior toD,interiorto Dbut exterior to C,and exterior to both C and D,respectively.Show thatg(Fi) = g(F22) and g(Fi12) = g(F21), where g(Fu) := feF,(d(f) - 2).b)i)Draw the medial graph of theHerschel graph (Figure18.ib).ii)Deduce from (a) that if G is a plane graph and if either G or G*fails tosatisfy Grinberg's Identity, then its medial graph has no Hamilton decom-position.ii) Conclude that the medial graph of the Herschel graph is a 4-connected4-regular plane graph which admits no Hamilton decomposition.(J.A.BONDY AND R. HAGGKVIST)
18.4 Path Exchanges and Parity 497 ii) the graph H of Figure 18.20, in which two vertices are of degree four and the rest are of degree three, has a unique Hamilton cycle. (R.C. Entringer and H. Swart) G H e x y Fig. 18.20. Construction of a uniquely hamiltonian almost cubic graph ————— ————— 18.4.4 Show that every cubic bipartite graph on at least four vertices has an even number of Hamilton cycles. (A. Kotzig) 18.4.5 a) Let G be a simple cubic graph. Show that the line graph of G admits a Hamilton decomposition if and only if G is 3-edge-colourable. (A. Kotzig) b) Deduce that the line graph of the Petersen graph is a 4-connected 4-regular graph which admits no Hamilton decomposition. 18.4.6 a) Let G be a 4-regular plane graph that admits a decomposition into two Hamilton cycles, C and D. Denote by F11, F12, F21, and F22 the sets of faces of G interior to both C and D, interior to C but exterior to D, interior to D but exterior to C, and exterior to both C and D, respectively. Show that g(F11) = g(F22) and g(F12) = g(F21), where g(Fij ) := f∈Fij (d(f) − 2). b) i) Draw the medial graph of the Herschel graph (Figure 18.1b). ii) Deduce from (a) that if G is a plane graph and if either G or G∗ fails to satisfy Grinberg’s Identity, then its medial graph has no Hamilton decomposition. iii) Conclude that the medial graph of the Herschel graph is a 4-connected 4-regular plane graph which admits no Hamilton decomposition. (J.A. Bondy and R. Haggkvist) ¨