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

Concept

A Hamiltonian cycle is a closed walk in a graph that visits every vertex exactly once before returning to the start — exactly the "visit each city once and return" trip the question describes. This is different from an Euler circuit, which instead must traverse every edge exactly once and requires every vertex to have even degree; Euler circuits are not relevant here because the constraint in this question is on cities (vertices), not on roads (edges).

A useful fact for checking existence: if a vertex has degree 2, both of its incident edges must be part of any Hamiltonian cycle passing through it, since there is no alternative edge available. When several such degree-2 vertices are all forced to share the same one or two neighbours, this can force a neighbour to need more cycle-edges than a cycle allows — giving a quick way to rule a graph out.

Application

Figure (i) is a 4×4 grid graph (16 vertices). Labelling positions (row, column) with rows and columns numbered 1–4, an explicit closed route through every vertex is:

1. Traverse row 1 left to right: (1,1) → (1,2) → (1,3) → (1,4).

2. Drop to row 2 and traverse right to left, stopping one column early: (1,4) → (2,4) → (2,3) → (2,2).

3. Drop to row 3 and traverse left to right, stopping one column early: (2,2) → (3,2) → (3,3) → (3,4).

4. Drop to row 4 and traverse right to left across all four columns: (3,4) → (4,4) → (4,3) → (4,2) → (4,1).

5. Climb back up column 1 through row 3 and row 2: (4,1) → (3,1) → (2,1).

6. Close the cycle: (2,1) → (1,1).

This route touches all 16 vertices exactly once and returns to the start, so figure (i) admits the required trip.

Figure (ii) has 5 vertices. Two of them (call the top-left vertex and the bottom-right vertex) each connect to three other vertices; the remaining three vertices each connect to exactly those same two vertices and nothing else — each has degree 2.

1. Each of the three degree-2 vertices has only two edges available, both going to the top-left and bottom-right vertices, so any Hamiltonian cycle passing through one of them must use both of its edges — there is no other edge to substitute.

2. Applying this to all three degree-2 vertices forces all three of their edges toward the top-left vertex to be included in the cycle, which would give that single vertex three cycle-edges.

3. A Hamiltonian cycle can only use exactly two cycle-edges at every vertex, so three forced edges at one vertex is a contradiction.

4. Therefore figure (ii) cannot have a Hamiltonian cycle.

Cross-check

Running the same forcing argument from the bottom-right vertex instead of the top-left one gives an identical contradiction — all three degree-2 vertices equally force their edge toward the bottom-right vertex, again demanding three cycle-edges there. Both directions agree, confirming figure (ii) has no Hamiltonian cycle, while the explicit 16-step route above confirms figure (i) does.

So the trip described is possible for figure (i) but not for figure (ii).