For the graph below answer the following questions List the

For the graph below, answer the following questions: (List the sequence of vertices if yes).

(a) Does the graph have a Hamiltonian cycle? If yes, give such a cycle. If no, given an argument to show why no such cycle exists.

(b) Does the graph have a Hamiltonian path? If yes, give such a path. If no, give an argument to show why no such path exists.

Solution

(a) The graph has a Hamiltonian cycle. The cycle is C[V,E] where V={a, b, c, d, f, g, h, i} is the set of vertices and

E={ab, bc, cf, fe, ei, ih, hg, gd, da} is the set of edges.

(b) The graph has a Hamiltonian path because it has Hamiltonian cycle.