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: Recall the Degree Requirement for a Hamiltonian Cycle:
In any closed round trip that visits every city exactly once, each city must use exactly two of its highway connections, one to arrive and one to leave, so every city used in the cycle must have at least two highway connections available to it in the original network.
Step 2: Apply the Degree Check to Graph (i):
In the 4 by 4 grid, every one of the 16 cities has at least two direct highway connections to neighbouring cities, since even the four corner cities connect to two neighbours and interior cities connect to up to four neighbours. Because the grid is large and richly connected, it is straightforward to construct a snake like closed path that uses exactly two connections at every city and returns to the start after visiting all 16 cities, which directly demonstrates a valid trip.
Step 3: Apply the Degree Check to Graph (ii):
In the 5 city network of figure (ii), tracing the drawn segments shows that the connections are unevenly distributed, and forcing a route that uses exactly two highway connections at every one of the 5 cities while forming a single closed loop is not possible with the specific segments actually drawn; at least one city cannot be fitted into a two connection loop without either leaving another city stranded or reusing a road that does not exist in the figure. This confirms no closed round trip covering all 5 cities can be built from graph (ii).
Step 4: Final Answer:
Since graph (i) supports a valid two connections per city closed loop through all its cities while graph (ii) does not, the trip is possible only for (i).
\[ oxed{ ext{Option (A)}} \]