Question

Figures (i) and (ii) below represent intercity highway systems, where each black dot is a city and each line segment joining two dots is a direct highway between those two cities. Figure (i) is a 4 by 4 grid of cities connected only along the horizontal and vertical grid lines, with no diagonal roads. Figure (ii) has 5 cities joined by 6 highways in an irregular network with one extra interior city.

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:

Split the cities into two groups so that every road joins one group to the other, then check whether the two groups are equal in size.

Answer 1

The Correct Option is A

Step 1: Understand what is being asked.
The salesperson's trip, starting at a city, visiting every other city exactly once, and returning to the start, is what graph theory calls a Hamiltonian cycle: a closed loop along the highways that touches every city exactly once.

Step 2: Check figure (i), the 4 by 4 grid.
Figure (i) has \(16\) cities arranged in a 4 by 4 grid, joined only by horizontal and vertical roads. Color the cities like a checkerboard, alternating black and white so that every road joins a black city to a white city. In a 4 by 4 grid this gives exactly \(8\) black cities and \(8\) white cities.
A closed loop that only ever moves between a black city and a white city must alternate colors at every step, so a loop covering all \(16\) cities needs equal numbers of both colors, which \(8\) and \(8\) satisfy. Such a loop can be built directly: starting at the top left city, go straight down the first column, then snake across the remaining columns row by row, and close the loop back along the top row. Every consecutive pair in this route is a real horizontal or vertical road, and all \(16\) cities appear exactly once. So a valid trip exists for figure (i).

Step 3: Check figure (ii), the 5-city network.
Figure (ii) has \(5\) cities. Two of them, call them \(A\) and \(E\), are each joined directly to all of the other three cities, call them \(B\), \(C\), and \(D\), while \(B\), \(C\), and \(D\) are not joined to each other at all, and \(A\) is not joined directly to \(E\) either.
This means every road in figure (ii) joins a city from the group \(\{A,E\}\) to a city from the group \(\{B,C,D\}\); no road stays inside either group.
A closed loop through such a network must also alternate between the two groups at every step, just like in figure (i). But here the groups have \(2\) and \(3\) cities, which are not equal. To keep alternating while visiting \(B\), \(C\), and \(D\), the loop needs to step back into the \(\{A,E\}\) group three times as well, yet that group only has \(2\) cities to offer. There are not enough cities in the smaller group to alternate with all \(3\) cities of the larger group, so the loop cannot close after visiting every city exactly once.

Step 4: Conclude.
A valid trip exists for figure (i) but not for figure (ii).
\[ \boxed{\text{Such a trip is possible for (i), but not for (ii).}} \]