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 traceable474 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, Hamilton￾connected 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