GATE 2026 CS (CS2) – Question 8
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?
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: (A) Such a trip is possible for (i), but not for (ii).
Explanation
The required trip is a Hamiltonian cycle: start at one city, visit every other city exactly once, and return to the starting city. In figure (i), such a cycle exists. In figure (ii), the two degree-2 vertices force a smaller cycle that leaves another vertex out, so a Hamiltonian cycle is impossible. Therefore, option (A) is correct.