J.A. BondyU.S.R. MurtyGraph Theory (III) Springer
J.A. Bondy U.S.R. Murty Graph Theory ABC Graph Theory (III)
ContentsGraphs11ed GraphTreesNonoleGrsSerTree-Search A35FlowsinNetw57omplexitAlg73lectivit0510PlanarGraph2431l TheFour-Colour Probler12Stable Sets and Cliqu9113TheProbabilisticMeth2514 VertexC015Cole16Matching17Edge Colour
Contents 1 Graphs ........................................................ 1 2 Subgraphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 3 Connected Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 4 Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99 5 Nonseparable Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117 6 Tree-Search Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135 7 Flows in Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157 8 Complexity of Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173 9 Connectivity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 205 10 Planar Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 243 11 The Four-Colour Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 287 12 Stable Sets and Cliques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 295 13 The Probabilistic Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 329 14 Vertex Colourings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 357 15 Colourings of Maps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 391 16 Matchings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 413 17 Edge Colourings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 451
XIIContents18 Hamilton Cycles47119 Coverings and Packings in Directed Graph50320 Electrical Networks52721IntegerFlowanco557Unsolved Problems08.References.GenealMath623Graph Pa625Operations and Relat627Families of Graphs629Struct631OtherNotatiol03Index637
XII Contents 18 Hamilton Cycles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 471 19 Coverings and Packings in Directed Graphs . . . . . . . . . . . . . . . . . . . 503 20 Electrical Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 527 21 Integer Flows and Coverings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 557 Unsolved Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 583 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 593 General Mathematical Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 623 Graph Parameters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 625 Operations and Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 627 Families of Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 629 Structures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 631 Other Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 633 Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 637
18Hamilton CyclesContentsTOUGHGRAPHS+HYPOHAMILTON18.2 NonhamilttonianPlanarGraphsBERG'ST+++++..++BARNETTE'S CONJE18.3 Path and Cycle ExchangePATHEXCHANGECYCLE EXCHANGESDIRAC'S THEOREMTHE CLOSURE OF A GRAPHTHE CHVATAL-ERDOSTHEOREM18.4 Path Exchanges and ParityTHELOLLIPOPLEMMAUNIQUELY HAMILTONIAN GRAPHSSHEEHAN'S CONJECTURE18.5 HamiCyclesinRm Graphs......OSAOSR18.6 Related Reading.BRIDGETHE HOPPING LEMLONG PATHS AND CYCLES18.1 Hamiltonian and Nonhamiltonian GraphsRecall that a path or cycle which contains every vertex of a graph is called aHamiltonpathor Hamiltoncycleof thegraph.Suchpathsand cycles arenamecafterSirWilliamRowanHamilton,whodescribed,inalettertohisfriendGravesin 1856, a mathematical game on the dodecahedron (Figure 18.la) in which one
18 Hamilton Cycles Contents 18.1 Hamiltonian and Nonhamiltonian Graphs . . . . . . . . . . 471 Tough Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 472 Hypohamiltonian Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . 473 18.2 Nonhamiltonian Planar Graphs . . . . . . . . . . . . . . . . . . . . 478 Grinberg’s Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 478 Barnette’s Conjecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 481 18.3 Path and Cycle Exchanges . . . . . . . . . . . . . . . . . . . . . . . . 483 Path Exchanges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 484 Cycle Exchanges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 485 Dirac’s Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 485 The Closure of a Graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 486 The Chvatal–Erd ´ os Theorem ˝ . . . . . . . . . . . . . . . . . . . . . . . . 488 18.4 Path Exchanges and Parity . . . . . . . . . . . . . . . . . . . . . . . . 492 The Lollipop Lemma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 492 Uniquely Hamiltonian Graphs . . . . . . . . . . . . . . . . . . . . . . . 494 Sheehan’s Conjecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 494 18.5 Hamilton Cycles in Random Graphs . . . . . . . . . . . . . . . 499 Posa’s Lemma ´ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 499 18.6 Related Reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 501 The Bridge Lemma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 501 The Hopping Lemma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 502 Long Paths and Cycles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 502 18.1 Hamiltonian and Nonhamiltonian Graphs Recall that a path or cycle which contains every vertex of a graph is called a Hamilton path or Hamilton cycle of the graph. Such paths and cycles are named after Sir William Rowan Hamilton, who described, in a letter to his friend Graves in 1856, a mathematical game on the dodecahedron (Figure 18.1a) in which one
47218 Hamilton Cyclesperson sticks pins in any five consecutive vertices and the other is required to comlottlformed to a spanning cycle (see Biggs et al. (1986) or Hamilton(1931). Hamilton was prompted to consider such cycles in his early investigationsinto group theory, the three edges incident to a vertex corresponding to threegenerators of a groupA graph is traceable if it contains a Hamilton path, and hamiltonian if it contains a Hamilton cycle. The dodecahedron is hamiltonian; a Hamilton cycle isindicated inFigure18.la.On the other hand,the Herschel graphof Figure18.1bis nonhamiltonian, because it is bipartite and has an odd number of vertices. Thisgraph is, however, traceable(a)(b)Fig. 18.1. Hamiltonian and nonhanmiltonian graphs: (a) the dodecahedron, (b) the Herschel graphTOUGH GRAPHSAs we saw in Section 8.3, the problem of deciding whether a given graph is hamiltonian is NP-complete. It is therefore natural to look for reasonable necessarysufficient conditions for the existence of Hamilton cycles. The following simplenecessary condition turns out to be surprisingly useful.Theorem 18.1 Let S be a set of vertices of a hamiltonian graph G. Then(18.1)c(G - S) ≤ISIMoreover, if equality holds in (18.1), then each of the [S] components of G -2tracableandeeryHamiltoncyceGincludsHamitonpathiachfthcomponents.Proof Let C be a Hamilton cycle of G. Then C - S clearly has at most [SlOnents. But this implies that G- S also has at most Js] components, becauseC is a spanning subgraph of G
472 18 Hamilton Cycles person sticks pins in any five consecutive vertices and the other is required to complete the path so formed to a spanning cycle (see Biggs et al. (1986) or Hamilton (1931)). Hamilton was prompted to consider such cycles in his early investigations into group theory, the three edges incident to a vertex corresponding to three generators of a group. A graph is traceable if it contains a Hamilton path, and hamiltonian if it contains a Hamilton cycle. The dodecahedron is hamiltonian; a Hamilton cycle is indicated in Figure 18.1a. On the other hand, the Herschel graph of Figure 18.1b is nonhamiltonian, because it is bipartite and has an odd number of vertices. This graph is, however, traceable. (a) (b) Fig. 18.1. Hamiltonian and nonhamiltonian graphs: (a) the dodecahedron, (b) the Herschel graph Tough Graphs As we saw in Section 8.3, the problem of deciding whether a given graph is hamiltonian is N P-complete. It is therefore natural to look for reasonable necessary or sufficient conditions for the existence of Hamilton cycles. The following simple necessary condition turns out to be surprisingly useful. Theorem 18.1 Let S be a set of vertices of a hamiltonian graph G. Then c(G − S) ≤ |S| (18.1) Moreover, if equality holds in (18.1), then each of the |S| components of G − S is traceable, and every Hamilton cycle of G includes a Hamilton path in each of these components. Proof Let C be a Hamilton cycle of G. Then C − S clearly has at most |S| components. But this implies that G−S also has at most |S| components, because C is a spanning subgraph of G
18.1 Hamiltonian and Nonhamiltonian Graphs473If G - S has exactly [SI cponents, C - S also has exactly [S| componenand the components of C- S are spanning subgraphs of the components of G- SIn other words, C includes a Hamilton path in each component of G - S.口A graph G is called tough if (18.1) holds for every nonempty proper subset Sof V.By Theorem 18.1, a graph which is not tough cannot behamiltonian.As anillustration, consider the graph G of Figure 18.2a. This graph has nine vertices.On deleting the set S of three vertices indicated, four components remain.Thisshows that the graph is not tough, and we infer from Theorem 18.1 that it isnonhamiltonianAlthough condition (18.1) has a simple form, it is not always easy to apply. Infact, as was shown by Bauer et al. (1990), recognizing tough graphs is Np-hard.。A(a)(b)Fig. 18.2. (a) A nontough graph G, (b) the components of G - SHYPOHAMILTONIAN GRAPHSAs the above example shows, Theorem 18.1 can sometimes be applied to deducethat a graph is nonhamiltonian. Such an approach does not always work. ThePetersen graph is nonhamiltonian (Exercises 2.2.6, 17.1.8), but one cannot deducethis fact from Theorem 18.1. Indeed, the Petersen graph has a very special property: not only is it nonhamiltonian, but the deletion of any one vertex results iniltonian graph (Exercise18.1.16a).Such graphs arecalled hypohamitonianahanDeleting a single vertex from a hypohamiltonian graph results in a subgraph withjustoneconit, and deleting a set S of at least two vertices produces no morethan [s] - 1 components, because each vertex-deleted subgraph is hamiltonian.hence tough.The Petersen graph is an example of a vertex-transitive hvpohamiltonian graph. Such graphs appear to be extremely rare. Another example is theCoreter graph (see Exercises 18.1.14 and 18.1.16c); the attractive drawing of thisgraph shown in Figure 18.3 is due to Randic (1981). Its geetric origins andmany of its interesting properties are described in Coxeter (1983)
18.1 Hamiltonian and Nonhamiltonian Graphs 473 If G − S has exactly |S| components, C − S also has exactly |S| components, and the components of C −S are spanning subgraphs of the components of G−S. In other words, C includes a Hamilton path in each component of G − S. A graph G is called tough if (18.1) holds for every nonempty proper subset S of V . By Theorem 18.1, a graph which is not tough cannot be hamiltonian. As an illustration, consider the graph G of Figure 18.2a. This graph has nine vertices. On deleting the set S of three vertices indicated, four components remain. This shows that the graph is not tough, and we infer from Theorem 18.1 that it is nonhamiltonian. Although condition (18.1) has a simple form, it is not always easy to apply. In fact, as was shown by Bauer et al. (1990), recognizing tough graphs is N P-hard. (a) (b) Fig. 18.2. (a) A nontough graph G, (b) the components of G − S Hypohamiltonian Graphs As the above example shows, Theorem 18.1 can sometimes be applied to deduce that a graph is nonhamiltonian. Such an approach does not always work. The Petersen graph is nonhamiltonian (Exercises 2.2.6, 17.1.8), but one cannot deduce this fact from Theorem 18.1. Indeed, the Petersen graph has a very special property: not only is it nonhamiltonian, but the deletion of any one vertex results in a hamiltonian graph (Exercise 18.1.16a). Such graphs are called hypohamiltonian. Deleting a single vertex from a hypohamiltonian graph results in a subgraph with just one component, and deleting a set S of at least two vertices produces no more than |S| − 1 components, because each vertex-deleted subgraph is hamiltonian, hence tough. The Petersen graph is an example of a vertex-transitive hypohamiltonian graph. Such graphs appear to be extremely rare. Another example is the Coxeter graph (see Exercises 18.1.14 and 18.1.16c); the attractive drawing of this graph shown in Figure 18.3 is due to Rand´ıc (1981). Its geometric origins and many of its interesting properties are described in Coxeter (1983)
47418 Hamilton CyclesFig.18.3.The Coxeter graphExercises18.1.1 By applying Theorem 18.1, show that the Herschel graph (Figure 18.1b)is nonhamiltonian.(It is.in fact,the smallest nonhamiltonian 3-connected planagraph.)18.1.2 Let G be a cubic graph, and let H be the cubic graph obtained from G byexpanding a vertex to a triangle, Exhibit a bijection between the Hamilton cyclesof G and those of H.18.1.3 Show that the Meredith graph (Figure 17.6) is nonhamiltonian18.1.4a) Let G be a graph and let X be a nonempty proper subset of V. If G / X is anonhamiltoniancubicgraph,showthatanypathofGeithermissesavertexof VX or has an end in VXb) Construct a nontraceable 3-connected cubic graph.18.1.5Find a3-connected planarbipartitegraph onfourteenverticeswhich isnotraceable18.1.6 A graph is traceable from a verter r if it has a Hamilton r-path, Hamiltoncted if any two vertices are connected by a Hamilton path, and 1-hamiltonianif it and all its vertex-deleted subgraphs are hamiltonianLet G be a graph and let H be the graph obtained from G by adding a new vertexand joining it to every vertex of G.Show thata) H is hamiltonian if and only if G is traceable
474 18 Hamilton Cycles Fig. 18.3. The Coxeter graph Exercises 18.1.1 By applying Theorem 18.1, show that the Herschel graph (Figure 18.1b) is nonhamiltonian. (It is, in fact, the smallest nonhamiltonian 3-connected planar graph.) 18.1.2 Let G be a cubic graph, and let H be the cubic graph obtained from G by expanding a vertex to a triangle. Exhibit a bijection between the Hamilton cycles of G and those of H. 18.1.3 Show that the Meredith graph (Figure 17.6) is nonhamiltonian. 18.1.4 a) Let G be a graph and let X be a nonempty proper subset of V . If G/X is a nonhamiltonian cubic graph, show that any path of G either misses a vertex of V \ X or has an end in V \ X. b) Construct a nontraceable 3-connected cubic graph. 18.1.5 Find a 3-connected planar bipartite graph on fourteen vertices which is not traceable. 18.1.6 A graph is traceable from a vertex x if it has a Hamilton x-path, Hamiltonconnected if any two vertices are connected by a Hamilton path, and 1-hamiltonian if it and all its vertex-deleted subgraphs are hamiltonian. Let G be a graph and let H be the graph obtained from G by adding a new vertex and joining it to every vertex of G. Show that: a) H is hamiltonian if and only if G is traceable
47518.1 Hamiltonian and Nonhamiltonian Graphsb) H is traceable from every vertex if and onlyifGis traceableH is Hamilton-connected if and only if G is traceable from every vertex,d) H is 1-hamiltonian if and only if G is hamiltonian.18.1.7a) Show that the graph of Figure 18.4 is 1-hamiltonian but not Hamiltonconnected.(T. ZAMFIRESCU)Fig.18.4. A 1-hamnilton-connected (Exercise 18.1.7)liangraphwlb) Find a Hamilton-connected graph which is not 1-hamiltonian18.1.8 Find a 2-diregular hypohamiltonian digraph on six vertic(J.-L. FOUQUET AND J.-L. JOLIVET)18.1.9 k-WALKgraph is a spanning closed walk which visits each vertex at mostAk-walkink times. (Thus a 1-walk is a Hamilton cycle.) If G has a k-walk, show that G is(1/k)-tough(Jackson and Wormald (1990) showed that, for k ≥ 3, every (1/(k - 2)-toughgraph has a k-walk.)18.1.10 PATH PARTITION NUMBERa partition of its vertex set into paths. The pathA pathpartition of agraphisnumber of a graph G, denoted r(G), is the minimum number of pathspartitiorinto which its vertex set V can be partitioned. (Thus traceable graphs are thosewhose path partition number is one.) Let G be a graph containing an edge e whichlies in no Hamiton cycle, and let H be the graph formed by taking m disjointcopies of G and adding all possible edges between the ends of the m copies of eso asto form a cliqueof2mvertices.Showthat thepathpartitionnumber of Hisatleastm/218.1.11 A graph G is path-tough if (G-S) ≤JS) for every proper subset S ofV
18.1 Hamiltonian and Nonhamiltonian Graphs 475 b) H is traceable from every vertex if and only if G is traceable, c) H is Hamilton-connected if and only if G is traceable from every vertex, d) H is 1-hamiltonian if and only if G is hamiltonian. 18.1.7 a) Show that the graph of Figure 18.4 is 1-hamiltonian but not Hamiltonconnected. (T. Zamfirescu) Fig. 18.4. A 1-hamiltonian graph which is not Hamilton-connected (Exercise 18.1.7) b) Find a Hamilton-connected graph which is not 1-hamiltonian. 18.1.8 Find a 2-diregular hypohamiltonian digraph on six vertices. (J.-L. Fouquet and J.-L. Jolivet) 18.1.9 k-Walk A k-walk in a graph is a spanning closed walk which visits each vertex at most k times. (Thus a 1-walk is a Hamilton cycle.) If G has a k-walk, show that G is (1/k)-tough. (Jackson and Wormald (1990) showed that, for k ≥ 3, every (1/(k − 2))-tough graph has a k-walk.) 18.1.10 Path Partition Number A path partition of a graph is a partition of its vertex set into paths. The path partition number of a graph G, denoted π(G), is the minimum number of paths into which its vertex set V can be partitioned. (Thus traceable graphs are those whose path partition number is one.) Let G be a graph containing an edge e which lies in no Hamilton cycle, and let H be the graph formed by taking m disjoint copies of G and adding all possible edges between the ends of the m copies of e, so as to form a clique of 2m vertices. Show that the path partition number of H is at least m/2. 18.1.11 A graph G is path-tough if π(G−S) ≤ |S| for every proper subset S of V
47618 Hamilton Cyclesa) Show that:i) every hamiltonian graph is path-tough,ii) every path-tough graph is tough.b) Give an example of a nonhamiltonian path-tough graph18.1.12 Let G be a vertex-transitive graph of prime order. Show that G is hamiltonian.18.1.13 Let G be the graph whose vertices are the thirty-five 3-element subsets of[1, 2,3, 4, 5, 6, 7], two vertices being joined if the subsets are disjoint. Let X be aset of vertices of G forming a Fano plane. Show that G - X is isomorphic to theCoxeter graph.18.1.14Show that the Petersen graph, the Coxeter graph, and the two graphsderived from them by expanding each vertex to a triangle, are all vertex-transitivenonhamiltonian graphs. (These four graphs are the only examples of such graphsknown.)18.1.15A graph is marimally nonhamitonian if it is nonhamiltonian but everypair of nonadjacent vertices are connected by a Hamilton patha) Show that:i) the Petersen graph and the Coxeter graph are maximally nonhamitoniani) the Herschel graph is not maximally nonhamiltonianb)Findamaximalynonhamitonianspanning supergraphof the Herschel graph.18.1.16 Show that:a) the Petersen graph is hypohamiltonian.b) there is no smaller hypohamiltonian graph(J.C. HERZ, J.J. DUBY, AND F. VIGUE)C) the Coxeter graph is hypohamiltonian.18.1.17 HYPOTRACEABLE GRAPHAgraph is hpotraceableifit isnot traceable but eachof its vertex-deleted subgraphs is traceable. Show that the graph in Figure18.5 is hypotraceable(C. THOMASSEN)18.1.18 PANCYCLIC GRAPHA simple graph on n vertices is pancyclic if it contains at leane cycle of eachlength1.3<1<na) Let G be a simple graph and v a vertex of G. Suppose that G-u is hamiltonianand that d(u) ≥ n/2. Show that G is pancyclic.b) Prove, by induction on n, that if G is a simple hamiltonian graph with more(J.A. BONDY; C. THOMASSEN)thann/4 edges,then Gis pancyclic
476 18 Hamilton Cycles a) Show that: i) every hamiltonian graph is path-tough, ii) every path-tough graph is tough. b) Give an example of a nonhamiltonian path-tough graph. 18.1.12 Let G be a vertex-transitive graph of prime order. Show that G is hamiltonian. 18.1.13 Let G be the graph whose vertices are the thirty-five 3-element subsets of {1, 2, 3, 4, 5, 6, 7}, two vertices being joined if the subsets are disjoint. Let X be a set of vertices of G forming a Fano plane. Show that G − X is isomorphic to the Coxeter graph. ————— ————— 18.1.14 Show that the Petersen graph, the Coxeter graph, and the two graphs derived from them by expanding each vertex to a triangle, are all vertex-transitive nonhamiltonian graphs. (These four graphs are the only examples of such graphs known.) 18.1.15 A graph is maximally nonhamiltonian if it is nonhamiltonian but every pair of nonadjacent vertices are connected by a Hamilton path. a) Show that: i) the Petersen graph and the Coxeter graph are maximally nonhamiltonian, ii) the Herschel graph is not maximally nonhamiltonian. b) Find a maximally nonhamiltonian spanning supergraph of the Herschel graph. 18.1.16 Show that: a) the Petersen graph is hypohamiltonian, b) there is no smaller hypohamiltonian graph, (J.C. Herz, J.J. Duby, and F. Vigue)´ c) the Coxeter graph is hypohamiltonian. 18.1.17 Hypotraceable Graph A graph is hypotraceable if it is not traceable but each of its vertex-deleted subgraphs is traceable. Show that the graph in Figure 18.5 is hypotraceable. (C. Thomassen) 18.1.18 Pancyclic Graph A simple graph on n vertices is pancyclic if it contains at least one cycle of each length l, 3 ≤ l ≤ n. a) Let G be a simple graph and v a vertex of G. Suppose that G−v is hamiltonian and that d(v) ≥ n/2. Show that G is pancyclic. b) Prove, by induction on n, that if G is a simple hamiltonian graph with more than n2/4 edges, then G is pancyclic. (J.A. Bondy; C. Thomassen)
47718.1 Hamiltonian and Nonhamiltonian GraphsFig. 18.5. A hyeable graphc) For all n ≥ 4, give an example of a simple graph G with n? /4 edges which ishamiltonian but not pancyclic.18.1.19 A simple graph on n vertices is uniquely pancyclic if it contains preciselyone cycle of each length l, 3≤1 ≤ n.a)For= 3,5, 8,14, find a uniquely pancyclic graph on n verticesb) Let G be a uniquely pancyclic graph. Show that:i) m ≥ (n -1) +log2(n-1),i)ifn=(r+)+2,thenm≤n+r-1.18.1.20 Let D be a 2-strong tournament, and let (r, y) be an arc of D such thad-() + d+(y) ≥ n - 1. Show that (z,y) lies in a directed cycle of each length l,3≤l≤n.(A. YEO)18.1.21 Let H bevertex-deleted subgraph of the Petersen graph P. Define ssequence G, i ≥ 0, of 3-connected cubic graphs, as follows.D Go=P.Gi+1 is obtained from G, and u(G.) copies (Hu : u E V(G.)) of H, by splittingDeach vertex u of G, into three vertices of degree one and identifying thesevertices with the three vertices of degree two in HySet G := Gk.(a) Show thati)n=10.gk,i) the circumference of G is 9.8= cn, where = log 8/log 9, and c is asuitable positive constantb) By appealing to Exercise 9.1.13, deduce that G has no path of length morethan Cn, where is a suitable positive constant
18.1 Hamiltonian and Nonhamiltonian Graphs 477 Fig. 18.5. A hypotraceable graph c) For all n ≥ 4, give an example of a simple graph G with n2/4 edges which is hamiltonian but not pancyclic. 18.1.19 A simple graph on n vertices is uniquely pancyclic if it contains precisely one cycle of each length l, 3 ≤ l ≤ n. a) For n = 3, 5, 8, 14, find a uniquely pancyclic graph on n vertices. b) Let G be a uniquely pancyclic graph. Show that: i) m ≥ (n − 1) + log2(n − 1), ii) if n = r+1 2 + 2, then m ≤ n + r − 1. 18.1.20 Let D be a 2-strong tournament, and let (x,y) be an arc of D such that d−(x) + d+(y) ≥ n − 1. Show that (x,y) lies in a directed cycle of each length l, 3 ≤ l ≤ n. (A. Yeo) 18.1.21 Let H be a vertex-deleted subgraph of the Petersen graph P. Define a sequence Gi, i ≥ 0, of 3-connected cubic graphs, as follows. G0 = P. Gi+1 is obtained from Gi and v(Gi) copies (Hv : v ∈ V (Gi)) of H, by splitting each vertex v of Gi into three vertices of degree one and identifying these vertices with the three vertices of degree two in Hv. Set G := Gk. a) Show that: i) n = 10 · 9k, ii) the circumference of G is 9 · 8k = cnγ, where γ = log 8/ log 9, and c is a suitable positive constant. b) By appealing to Exercise 9.1.13, deduce that G has no path of length more than c nγ, where c is a suitable positive constant.