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 hamil￾tonian. 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 sub￾graphs 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)