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?
Show Hint
Treat each figure as a graph and check whether a Hamiltonian cycle, a closed tour hitting every city once, can be drawn on it.
Such a trip is possible for (i), but not for (ii).
Such a trip is possible for (ii), but not for (i).
Such a trip is possible for both (i) and (ii).
Such a trip is possible neither for (i) nor for (ii).
Show Solution
Verified By Collegedunia
The Correct Option isA
Solution and Explanation
Step 1: Restate the problem as a graph theory question.
The salesperson wants a closed route that starts at one city, visits every other city exactly once, and returns to the start. This is exactly a Hamiltonian cycle: a cycle in a graph that passes through every vertex exactly once. Figure (i) has 16 cities laid out as a 4 by 4 grid, joined by the horizontal and vertical roads shown. Figure (ii) has 5 cities joined by 6 roads.
Step 2: Test figure (i).
A rectangular grid graph with \( m \) rows and \( n \) columns always has a Hamiltonian cycle when \( m \times n \) is even, since the cities can be covered by weaving down one set of columns and weaving back through the rest without repeating a city. Here \( m = n = 4 \), so \( mn = 16 \), which is even, so a valid closed tour exists that hits all 16 cities once and returns to the start. So the trip is possible for (i).
Step 3: Test figure (ii).
Name the 5 cities A (top left), B (top right), C (the inner point), D (left), and E (bottom), matching the figure. Reading the roads gives the pairs A-B, A-C, A-D, D-E, C-E, and E-B. Cities B, C, and D each sit on only two roads, and in each case both roads lead to A or to E. In a Hamiltonian cycle every city uses exactly two of its roads, so with only two roads available at B, C, and D, both roads at each of them must be part of the cycle. That forces all six roads, A-B, A-C, A-D, D-E, C-E, E-B, into the cycle at once. But then city A would carry three roads (to B, C, and D) in the cycle, while a simple cycle can use only two roads at any one city. This contradiction shows no Hamiltonian cycle can be built in (ii).
Final Answer:
A full round trip is possible for (i), the 4 by 4 grid, but not for (ii), the 5-city network.
\[ \boxed{\text{Option A}} \]
