Figures (i) and (ii) represent intercity highway systems. The black dots…

The required trip is a Hamiltonian cycle: it must start at a city, visit every other city exactly once, and return to the start. In figure (i), the 4 x 4 grid has such a cycle; for example, one can move along the top row, down the right side, snake through the inner rows, and return through the left side to the starting city. In figure (ii), label the top-left and bottom-right vertices as the two common endpoints. The top-right, centre, and bottom-left vertices each have degree 2 and are adjacent only to those same two endpoints. In any Hamiltonian cycle, each of these degree-2 vertices would have to use both of its incident edges, forcing the two common endpoints to have three cycle edges each, which is impossible. Therefore the trip is possible for (i), but not for (ii).