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.