Figures (i) and (ii) represent intercity highway systems. The black dots represent cities and the li

Q: What is GATE-CS?

GATE-CS is a competitive examination conducted in India. This question is from the 2026 GATE-CS Aptitude paper.

Q: How can I prepare for GATE-CS Aptitude?

To prepare for GATE-CS Aptitude, practice previous year questions (PYQs), understand concepts thoroughly, and solve mock tests regularly. This 2026 question covers Analytical Aptitude topic.

Q: What is the difficulty level of this question?

This GATE-CS 2026 Aptitude question has a medium difficulty level.

Q: Where can I find more GATE-CS previous year questions?

You can find more GATE-CS previous year questions on AspirantMitraa. Browse by subject, topic, year, and difficulty level to practice effectively.

Question

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 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?

Accepted Answer

Correct Answer: (A) Such a trip is possible for (i), but not for (ii).Concept -- Hamiltonian Cycle Existence: A trip that visits every vertex exactly once and returns to the start is called a Hamiltonian cycle. Graph (i) is designed such that a Hamiltonian cycle exists (e.g., one can traverse all cities in a closed loop). Graph (ii) contains a vertex of degree 1 (a leaf) – such a vertex cannot be part of any Hamiltonian cycle because a cycle requires each vertex to have degree at least 2. Thus no Hamiltonian cycle exists in (ii).Why other options are incorrect: • B – Opposite of the correct answer; (ii) has a vertex of degree 1, making a Hamiltonian cycle impossible.• C – False because (ii) lacks a Hamiltonian cycle.• D – False because (i) does have a Hamiltonian cycle.Note: A necessary condition for a Hamiltonian cycle is that every vertex must have degree at least 2 (no leaf nodes). A sufficient condition (Dirac’s theorem) states that if every vertex has degree ≥ n/2, then the graph is Hamiltonian. However, here we simply observe the leaf.

Master GATE-CS with Our Test Series

More Questions from Analytical Aptitude

Frequently Asked Questions

Master GATE-CS with Our Test Series

More Questions from Analytical Aptitude

Frequently Asked Questions