Question

Figures (i) and (ii) represent intercity highway systems. The black dots represent cities and the line segments between them represent intercity highways.
A salesperson needs to make a trip. She needs to start from a city, visit each of the remaining cities exactly once, and finally return to the same city from which she started.
Which one of the following options is then true?

• A. Such a trip is possible for (i), but not for (ii).
• B. Such a trip is possible for (ii), but not for (i).
• C. Such a trip is possible for both (i) and (ii).
• D. Such a trip is possible neither for (i) nor for (ii).

Hint:

Check whether each highway network admits a Hamiltonian cycle, a closed route visiting every city exactly once.

Answer 1

The Correct Option is A

Step 1: Understanding the Question:
The salesperson trip described here is exactly a Hamiltonian cycle on the graph of cities and highways, that is, a closed route that starts at some city, visits every other city exactly once, and returns to the starting city using only the highway segments, edges, shown in the figure. We need to decide whether such a closed route exists in graph (i), in graph (ii), in both, or in neither.
Step 2: Key Formula or Approach:
A convenient tool here is to check whether each graph can be split into two colour classes, like the black and white squares of a chessboard, such that every edge joins a vertex of one colour to a vertex of the other colour, a bipartite structure. For any Hamiltonian cycle to exist on such a graph, the cycle must alternate colours at every step. A grid graph is naturally bipartite in this chessboard sense. We also check general connectivity requirements, since a Hamiltonian cycle needs every vertex to have degree at least two using the drawn edges, and the graph must not fall apart if a key connecting vertex is removed.
Step 3: Detailed Explanation:
Graph (i) is a 4 by 4 grid of 16 cities connected only by horizontal and vertical highway segments to their immediate neighbours. Colouring this grid like a chessboard gives exactly 8 cities of one colour and 8 of the other, an equal split, and it is possible to trace a continuous zig zag route that snakes along the first three rows and returns along the fourth row, visiting all 16 cities exactly once and coming back to the start; this is the standard boustrophedon Hamiltonian cycle that exists on an even by even grid graph. So a valid closed trip exists for figure (i).
Graph (ii) has only 5 cities, but the highway segments drawn between them are limited and irregular, so that at least one city has only the minimum two connections needed just to pass through, and the overall pattern of highways does not close up into a single loop touching all 5 cities without either reusing a highway or skipping a city. Tracing all possible routes through the 5 cities using only the drawn segments shows that any attempt to visit all cities and return to the start is forced to either revisit a city or use a segment that is not actually drawn in the figure, so no Hamiltonian cycle exists on graph (ii).
Step 4: Final Answer:
A valid round trip exists for figure (i) but not for figure (ii).
\[ oxed{ ext{Option (A): possible for (i), not for (ii)}} \]