Figures and 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?
View worked solution
Answer: A
The problem asks whether a Hamiltonian cycle (a closed loop that visits every city exactly once and returns to the starting city) exists in the given highway systems.
- For Figure (i): A Hamiltonian cycle exists. We can easily trace a continuous loop that visits every vertex exactly once and returns to the starting vertex.
- For Figure (ii): The graph contains a cut-vertex (a central vertex whose removal disconnects the graph into two separate components). To visit the cities in both components and return to the start, any cycle must pass through this cut-vertex at least twice. Since a Hamiltonian cycle requires visiting every vertex exactly once, no such trip is possible for Figure (ii).
Therefore, such a trip is possible for (i), but not for (ii).
Free practice · Your answers on this page are not saved.