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 ofV18.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 Hamilton￾connected. (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