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
A full round trip needs exactly two highways used at every city; check whether that is possible at every city in each figure.
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: Understand what the question is asking.
The salesperson wants to start at a city, visit every other city exactly once, and come back to the start. In graph terms, this trip exists exactly when the graph has a Hamiltonian cycle, a closed loop that passes through every vertex exactly once using only the given edges.
Step 2: Check figure (i), the grid of 16 cities.
Figure (i) is a 4 by 4 grid of cities connected only to their horizontal and vertical neighbours. Label a city by its row and column as \((r,c)\), with \(r,c\) from 1 to 4. A Hamiltonian cycle can be built directly:
\[
(1,1)\to(1,2)\to(1,3)\to(1,4)\to(2,4)\to(2,3)\to(2,2)\to(3,2)\to(3,3)\to(3,4)\to(4,4)\to(4,3)\to(4,2)\to(4,1)\to(3,1)\to(2,1)\to(1,1)
\]
Every step here moves to a grid neighbour, all 16 cities appear exactly once, and the path closes back to the start. So a full round trip is possible for (i).
Step 3: Check figure (ii), the 5-city network.
Call the five cities \(V_1\) through \(V_5\), where \(V_1\) and \(V_5\) are the two cities with three highways each, and \(V_2,V_3,V_4\) are the three cities that each have only two highways. Since \(V_2\), \(V_3\), and \(V_4\) each touch only two highways, both of those highways must be used in any round trip through that city, because a round trip uses exactly two highways at every city it visits.
Step 4: See why this breaks down at \(V_1\).
Each of \(V_2\), \(V_3\), \(V_4\) has one of its two highways going to \(V_1\). Since all three of these highways must be used, \(V_1\) would need three highways used at once in the trip. But a round trip can only use two highways at each city, one to arrive and one to leave. Needing three at \(V_1\) is impossible, so no such round trip can exist for (ii).
Final Answer:
A full round trip exists for (i), the 4 by 4 grid, but not for (ii), the 5-city network.
\[ \boxed{\text{Possible for (i), not for (ii)}} \]
