The GATE Grind

GATE 2026 CS (CS2) – Question 8

General Aptitude · Analytical Aptitude: Logical Reasoning, Deduction and Analogy · 2 marks · Multiple choice

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?

Diagram for GATE 2026 CS (CS2) question 8
  1. Such a trip is possible for (i), but not for (ii).
  2. Such a trip is possible for (ii), but not for (i).
  3. Such a trip is possible for both (i) and (ii).
  4. Such a trip is possible neither for (i) nor for (ii).

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

All Analytical Aptitude: Logical Reasoning, Deduction and Analogy questions →