IAE Academy

GATE 2026 CS2 GA Q.8: solution and answer

GATE 2026 · CS2GA Q.8 · 2 marks · MCQ

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?

GATE 2026 CS2 GA question 8: Two graphs.Tap to open full size
Figure from the GATE 2026 CS2 paper. It is part of the question.
Figure description

Two graphs. Figure (i) is a 4 by 4 square grid of 16 black dots (cities), 4 rows and 4 columns, with a line segment joining each pair of horizontally adjacent dots and each pair of vertically adjacent dots (24 edges). Figure (ii) has 5 dots: A at top-left, B at top-right, C at the right-middle inside the shape, D at the left-lower side, E at the bottom. Line segments: A-B (top horizontal), A-C, A-D, B-E, C-E, D-E. So A and E each connect to B, C and D, and there are no other edges.

  1. (A)

    Such a trip is possible for (i), but not for (ii).

  2. (B)

    Such a trip is possible for (ii), but not for (i).

  3. (C)

    Such a trip is possible for both (i) and (ii).

  4. (D)

    Such a trip is possible neither for (i) nor for (ii).

Answer and solution

ANSWER

Option (A): such a trip is possible for (i), but not for (ii).

Official answer: ASource: Official answer key, GATE 2026 CS2 (IIT Guwahati)

  1. The trip described starts at a city, visits every other city exactly once and returns to the start. In graph terms it is a closed route through all the dots, a Hamiltonian cycle. Check each figure.

  2. Figure (i) is a grid of 16 cities. Label the cities by (row, column). A valid trip is: (1,1), (1,2), (1,3), (1,4), then down to (2,4), left to (2,3), (2,2), down to (3,2), right to (3,3), (3,4), down to (4,4), left to (4,3), (4,2), (4,1), then up to (3,1), (2,1), and back to (1,1). Each step moves along a highway. This covers cities, each once, and returns to the start. So the trip is possible for (i).

  3. Figure (ii) has 5 cities. Call them A (top-left), B (top-right), C (inner right), D (left) and E (bottom). The highways are A-B, A-C, A-D, B-E, C-E and D-E. So A and E are each joined only to B, C and D, and B, C and D are joined only to A and E.

  4. In any closed route, each city is entered once and left once, so it uses exactly 2 of its highways. A trip through all 5 cities uses exactly 5 highways.

  5. B, C and D each have only 2 highways, so the trip must use both highways at each of them. That is 6 highways, and no highway is counted twice, since none joins two of B, C, D. But the trip has only 5 highways. This is a contradiction.

  6. Equivalently, every highway joins one of to one of , so the cities alternate between the two groups along a closed route. That needs the groups to be equal in size, but they have 2 and 3 cities. So no such trip exists for (ii).

  7. Hence the trip is possible for (i) but not for (ii): option (A).

KEY IDEA

The trip is a closed route through every city once, a Hamiltonian cycle. A grid with an even number of rows or columns has one. A graph where all cities lie on two sides and the sides are unequal (here 2 and 3) cannot have one, because the route must alternate sides.

WATCH OUT FOR

Assuming a route can pass through a city twice, or that it need not return to the start. Another is to assume that having many highways in (i) guarantees a trip, or that few highways in (ii) is enough to rule one out, without actually finding the route or the contradiction.

From the GATE 2026 CS2 paper. Every question of this paper · Download the full paper · All 72 Reasoning questions, with notes

More Reasoning questions