《图论》课程教学资源（书籍文献）Graph Theory III（18-21，J.A. Bondy，U.S.R. Murty）

47818 Hamilton Cycles(Jackson (1986) has shown that every 3-connected cubic graph G has a cycle ofength atleast n?for asuitablepositive constant For all d >3.Jackson andParsons (1982)haveconstructed aninfinite familyofd-connectedd-regulargraphsG with circumference less than n?, where < 1 is a suitable positive constantdepending on d.)18.1.22 Let t be a positive real number. A connected graph G is t-tough if c(G -S) ≤ JS/t for every vertex cut S of V.(Thus 1-tough graphs are the same as toughgraphs.) The largest value of t for which a graph is t-tough is called its toughness.a) Determine the toughness of the Petersen graph.b) Show that every 1-tough graph on an even number of vertices has a 1-factor.) Consider the graph H described in Exercise 18.1.10, where G is the graphshown in Figure 18.6 and m = 5. Show that H v K2 is 2-tough but not path-tough (hence not hamiltonian)(D. BAUER, H.J. BROERSMA, AND H.J. VELDMAN)(Chvatal (1973) hased the existence of a constant t such that everycont-tough graph is hamiltonian.)Fig. 18.6. An element in the construction of a nonhamiltonian 2-tough graph (Exer-cise 18.1.22)18.2 Nonhamiltonian Planar GraphsGRINBERG'S THEOREMRecall (from Section 11.1) that Tait (1880) showed the Four-Colour Conjectureto be equivalent to the statement that every 3-connected cubic planar graph is3-edge-colourable, Tait thought that he had thereby proved Four-Colour Con-jecture, because he believed that every such graph was hamiltonian, and hence3-edge-colourable.However,Tutte(1946)showed this tobefalseby constructinga nonhamiltonian 3-connected cubic planar graph (depicted in Figure 18.7) usingingenious ad hoc arguments (Exercise 18.2.1). For many years, the Tutte graph was

478 18 Hamilton Cycles (Jackson (1986) has shown that every 3-connected cubic graph G has a cycle of length at least nγ for a suitable positive constant γ. For all d ≥ 3, Jackson and Parsons (1982) have constructed an infinite family of d-connected d-regular graphs G with circumference less than nγ, where γ < 1 is a suitable positive constant depending on d.) 18.1.22 Let t be a positive real number. A connected graph G is t-tough if c(G − S) ≤ |S|/t for every vertex cut S of V . (Thus 1-tough graphs are the same as tough graphs.) The largest value of t for which a graph is t-tough is called its toughness. a) Determine the toughness of the Petersen graph. b) Show that every 1-tough graph on an even number of vertices has a 1-factor. c) Consider the graph H described in Exercise 18.1.10, where G is the graph shown in Figure 18.6 and m = 5. Show that H ∨ K2 is 2-tough but not path￾tough (hence not hamiltonian). (D. Bauer, H.J. Broersma, and H.J. Veldman) (Chv´atal (1973) has conjectured the existence of a constant t such that every t-tough graph is hamiltonian.) e Fig. 18.6. An element in the construction of a nonhamiltonian 2-tough graph (Exer￾cise 18.1.22) 18.2 Nonhamiltonian Planar Graphs Grinberg’s Theorem Recall (from Section 11.1) that Tait (1880) showed the Four-Colour Conjecture to be equivalent to the statement that every 3-connected cubic planar graph is 3-edge-colourable. Tait thought that he had thereby proved Four-Colour Con￾jecture, because he believed that every such graph was hamiltonian, and hence 3-edge-colourable. However, Tutte (1946) showed this to be false by constructing a nonhamiltonian 3-connected cubic planar graph (depicted in Figure 18.7) using ingenious ad hoc arguments (Exercise 18.2.1). For many years, the Tutte graph was

47918.2NonhamiltonianPlanarGraphsFig.18.7.ttegraplthe only known enpleof a nonhamiltonian 3-connected cubic planargraph.Butthen Grinberg (1968) discovered a simple necessary condition for a plane graphto be hamiltonian. His discovery led to the construction of many nonhamiltonianplanar graphs.Theorem18.2GRINBERG'S THEOREMgraph with a Hamilton cycle C. ThenLetGbeaplan-2)( - ) = 0(18.2)where o and o are the numnbers of faces of degreei contained in Int C and ErC, respectively.Proof Denote by E' the subset of E(G))E(C) contained in Int C, and set m' :=|E'J. Then Int C contains exactly m’+1 faces (see Figure 18.8, where m' - 3 andthe four faces all have degree four).Therefore(18.3)0=m+1三Now each edge in E' lies on the booftusin Int C.and each edge ofC lies on the boundary of exactly one face in Int C. ThereforeZi0l=2m + n(18.4)

18.2 Nonhamiltonian Planar Graphs 479 Fig. 18.7. The Tutte graph the only known example of a nonhamiltonian 3-connected cubic planar graph. But then Grinberg (1968) discovered a simple necessary condition for a plane graph to be hamiltonian. His discovery led to the construction of many nonhamiltonian planar graphs. Theorem 18.2 Grinberg’s Theorem Let G be a plane graph with a Hamilton cycle C. Then n i=1 (i − 2)(φ i − φ i ) = 0 (18.2) where φ i and φ i are the numbers of faces of degree i contained in Int C and Ext C, respectively. Proof Denote by E the subset of E(G)\E(C) contained in Int C, and set m := |E |. Then Int C contains exactly m + 1 faces (see Figure 18.8, where m = 3 and the four faces all have degree four). Therefore n i=1 φ i = m + 1 (18.3) Now each edge in E lies on the boundary of two faces in Int C, and each edge of C lies on the boundary of exactly one face in Int C. Therefore n i=1 iφ i = 2m + n (18.4)

48018 Hamilton CyclesFig.18.8. An illustration for Grinberg's Identity (18.2)Using (18.3), we can eliminate m' from (18.4) to obtain(18.5)Likewise,(18.6)口Equations (18.5) and (18.6) now yield (18.2)Equation (18.2) is known as Grinberg's Identity. With the aid of this identity,itisaole mater to show,for example, that the Grinberg graph,depicted inFigure.9,isnonhamiltonian.SupposethatthisgraphishamiltonianNotingFig. 18.9. The Grinberg graph

480 18 Hamilton Cycles 4 4 4 4 4 5 5 Fig. 18.8. An illustration for Grinberg’s Identity (18.2) Using (18.3), we can eliminate m from (18.4) to obtain n i=1 (i − 2)φ i = n − 2 (18.5) Likewise, n i=1 (i − 2)φ i = n − 2 (18.6) Equations (18.5) and (18.6) now yield (18.2).
Equation (18.2) is known as Grinberg’s Identity. With the aid of this identity, it is a simple matter to show, for example, that the Grinberg graph, depicted in Figure 18.9, is nonhamiltonian. Suppose that this graph is hamiltonian. Noting Fig. 18.9. The Grinberg graph

18.2Nonhamiltonian Planar Graphs481that it only has faces of degrees five, eight, and nine, Grinberg's Identity (18.2)yields3( - ) + 6(s - ) + 7(% - ) = 0We deduce that7(g - ) = 0 (modulo 3)But this is clearly impossible, because the value of the left-hand side is 7 or -7depending on whether the unique face of degree nine lies in Int C or in Ext CTherefore the graph cannot be hamiltonian.The Grinberg graph is an example of a nonhamiltonian 3-connected essentilly4-edge-connected cubic planar graph. Tutte (1956) showed, on the other handthat every 4-connected planar graph is hamiltonian. (Thomassen (1983b) found ashorter proofof this theorem.but his proof is still too complicated to be presentedhere.Thebasicidea is discussed in Section 18.6.)In applying Grinberg's Identity,the parities of theface degrees play acrucial role. This approach fails to provide examples of bipartite nonhamiltonianonnectedcubicplanaraphs.Indeed.Barnette(1969).and independentlyKelR-CCmans and Lomonosov (1975),conjectured that there are nosuch graphs.BARNETTE'SCONJECTUREConjecture 18.3 Every 3-connected cubic planar bipartite graph is hamiltonianPlanbipartite graph was constructed by J. D. Horton (see Bondy and Murty (1976)p.240). The smallest example known of such a graph was found independently byKelmans(1986,1994)andGeorges(1989).Itisshown inFigure18.10Historical note. Interestingly, and ironically, Grinberg's Identity (18.2) wasknown already to Kirkman (1881), some ninety years earlier. But Kirkman, coivinced that every 3-connected cubic planar graph was hamiltonian, used it as atool in searching for Hamilton cycles in particular examples of such graphsIn the next section.we derive various sufficient conditions for hamiltonicityExercises18.2.1a) Show that no Hamilton cycle in the pentagonal prism (the graph Gr in Figre 18.11) can contain both of the edges e and elb) Using (a), show that no Hamiton cycle in the graph G2 can contain both ofthe edges e and e

18.2 Nonhamiltonian Planar Graphs 481 that it only has faces of degrees five, eight, and nine, Grinberg’s Identity (18.2) yields 3(φ 5 − φ 5 ) + 6(φ 8 − φ 8 ) + 7(φ 9 − φ 9 )=0 We deduce that 7(φ 9 − φ 9 ) ≡ 0 (modulo 3) But this is clearly impossible, because the value of the left-hand side is 7 or −7, depending on whether the unique face of degree nine lies in Int C or in Ext C. Therefore the graph cannot be hamiltonian. The Grinberg graph is an example of a nonhamiltonian 3-connected essentially 4-edge-connected cubic planar graph. Tutte (1956) showed, on the other hand, that every 4-connected planar graph is hamiltonian. (Thomassen (1983b) found a shorter proof of this theorem, but his proof is still too complicated to be presented here. The basic idea is discussed in Section 18.6.) In applying Grinberg’s Identity, the parities of the face degrees play a cru￾cial role. This approach fails to provide examples of bipartite nonhamiltonian 3-connected cubic planar graphs. Indeed, Barnette (1969), and independently Kel￾mans and Lomonosov (1975), conjectured that there are no such graphs. Barnette’s Conjecture Conjecture 18.3 Every 3-connected cubic planar bipartite graph is hamilto￾nian. Planarity is essential here. An example of a nonhamiltonian 3-connected cubic bipartite graph was constructed by J. D. Horton (see Bondy and Murty (1976), p.240). The smallest example known of such a graph was found independently by Kelmans (1986, 1994) and Georges (1989). It is shown in Figure 18.10. Historical note. Interestingly, and ironically, Grinberg’s Identity (18.2) was known already to Kirkman (1881), some ninety years earlier. But Kirkman, con￾vinced that every 3-connected cubic planar graph was hamiltonian, used it as a tool in searching for Hamilton cycles in particular examples of such graphs. In the next section, we derive various sufficient conditions for hamiltonicity. Exercises 18.2.1 a) Show that no Hamilton cycle in the pentagonal prism (the graph G1 in Fig￾ure 18.11) can contain both of the edges e and e . b) Using (a), show that no Hamilton cycle in the graph G2 can contain both of the edges e and e .

482181Fig. 18.10. The Kelectedcubicbipartiteesgraph:aneerapc) Using (b), show that every Hamilton cycle in the graph G3 must contain theedgeed) Deduce that the Tutte graph (Figure 18.7) is nonhamiltonian.G1G2GFig. 18.11. Threof the Tutte graphteosThecons18.2.2 Give pleofasimplenonacubicgraphofcoltoniativity two.18.2.3Let G =G, where Go is the plane graph Ka,and G, the plane triangulation obtained from Gi-1, i ≥ 1, by inserting a vertex in each face and joining ittothe three vertices on theboumdaryoftheface.LetIbe the circumference ofG.a) Show that n =2. (3*+ 1) and 1≤2k+2.b) Deduce that l < cnlog2/ log 3 for a suitable constant(J.W. MOON AND L. MOSER)

482 18 Hamilton Cycles Fig. 18.10. The Kelmans–Georges graph: a nonhamiltonian 3-connected cubic bipartite graph c) Using (b), show that every Hamilton cycle in the graph G3 must contain the edge e. d) Deduce that the Tutte graph (Figure 18.7) is nonhamiltonian. e e e e
e
G1 G2 G3 Fig. 18.11. Three steps in the construction of the Tutte graph 18.2.2 Give an example of a simple nonhamiltonian cubic planar graph of connec￾tivity two. 18.2.3 Let G = Gk, where G0 is the plane graph K4, and Gi the plane triangu￾lation obtained from Gi−1, i ≥ 1, by inserting a vertex in each face and joining it to the three vertices on the boundary of the face. Let l be the circumference of G. a) Show that n = 2 · (3k + 1) and l ≤ 2k+2. b) Deduce that l < cnlog 2/ log 3 for a suitable constant c. (J.W. Moon and L. Moser)