Question 8

A trip that starts at a city, visits every other city exactly once, and returns to the starting city is a Hamiltonian cycle.

1. Figure (i) is a $4 \times 4$ grid graph ($P_4 \square P_4$). Any $m \times n$ grid graph with at least one even dimension has a Hamiltonian cycle (for instance, snaking across the rows and returning along the left boundary column).
2. Figure (ii) is the complete bipartite graph $K_{2,3}$ with parts of sizes $2$ and $3$. Since a bipartite graph can only have cycles of even length and $|V| = 5$ is odd (or equivalently, the 3 vertices of degree 2 must all use both edges incident to the same 2 hub vertices, requiring $6$ edges at the hubs in a 5-cycle), Figure (ii) has no Hamiltonian cycle.

Thus, such a trip is possible for (i), but not for (ii).