GATE CSE 2026 | Set 2 | GA | Question: 8

Question

Figures $\text{(i)}$ and $\text{(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?

 

• A. Such a trip is possible for $\text{(i)}$, but not for $\text{(ii)}$.
• B. Such a trip is possible for $\text{(ii)}$, but not for $\text{(i)}$.
• C. Such a trip is possible for both $\text{(i)}$ and $\text{(ii)}$.
• D. Such a trip is possible neither for $\text{(i)}$ nor for $\text{(ii)}$.

Comments

Hamiltonian cycle concept

Answer 1

Hamiltonian cycle concept

Answer 2

Only Figure (i) satisfies the given Conditions.

$Concept:$ Hamiltonian Cycle or Circuit: A Hamiltonian Cycle or Circuit in a graph G is a cycle that visits each vertex of G exactly once and returns to the starting vertex.

Answer: $A$

Answer 3

BOTH figures should satisfy the given condition.
Because it is clearly written that "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."
It means you can visit your starting city multiple times(as condition is only on the remaining cities)and finally return to the starting city. 
in figure (ii) you visit all outer cities exactly once and return to starting city, you find that still one inner city remains.
you visit that inner city once and return to your  starting city finally.

Anyone has any better explanation?
is my explanation wrong?@GO Classes 

Answer 4

1. Highway System (i):
   • This system is a complete grid where each city is connected to its adjacent cities, forming a connected network. Each city has even degree connectivity, allowing traversal from one city to another until all cities are visited and the starting city is revisited. This makes it possible to find a Hamiltonian circuit.
2. Highway System (ii):
   • This system has an irregular layout with some cities having very high connectivity and others very low, making it difficult to visit all cities exactly once and return to the starting point without revisiting another city. Generally, such less symmetric and sparsely connected networks don't support forming a complete Hamiltonian circuit, meaning no such path exists for all cities.

Thus, the correct answer is: Such a trip is possible for (i), but not for (ii).