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 trip is a Hamiltonian cycle: every city must be visited once before returning. Label grid (i) by (row,column), starting at the top left. One valid tour is
(1,1)→(1,2)→(1,3)→(1,4)→(2,4)→(2,3)→(2,2)→(3,2)→(3,3)→(3,4)→(4,4)→(4,3)→(4,2)→(4,1)→(3,1)→(2,1)→(1,1).
In (ii), call the upper-left and bottom cities A,D. Each of the other three cities has exactly two incident roads, both leading to A and D. Visiting any such city in a cycle forces both its roads to be used. Visiting all three would therefore force three cycle edges at A, impossible because a cycle uses exactly two edges at each vertex.
Hence the trip is possible for **(i) only, A**. This is a vertex-visiting problem, not a requirement to traverse every road.
More Analytical Aptitude: Logical Reasoning, Deduction and Analogy questions
- GATE 2025 CS (CS1) Q4
- GATE 2025 CS (CS2) Q6
- GATE 2025 CS (CS2) Q7
- GATE 2025 CS (CS2) Q10
- GATE 2024 CS (CS1) Q1
- GATE 2024 CS (CS2) Q1
All Analytical Aptitude: Logical Reasoning, Deduction and Analogy questions →