Skip to content
GATEiit

GATE CSE 2026 Session 2 Q8: Round trip visiting every city once in two highway maps

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

Figure (i) is a 4 by 4 grid of 16 cities joined to their horizontal and vertical neighbours; figure (ii) is a graph of five cities where two cities of degree two both connect the same pair of cities
Tap the figure to enlarge

Try it: multiple choice: exactly one correct option

Select one option
Wrong answer costs 2/3 mark in GATE.
Show answer and explanation

Answer: A (official GATE 2026 final answer key)

Concept used: The trip is a Hamiltonian cycle; a degree-2 vertex forces both its edges into the cycle.

First step: In (ii), mark the edges forced by the two degree-2 cities and see whether the remaining city can still be included.

Full step-by-step solution

Detailed working, common mistakes and linked mock tests will be available with a free GATEiit account. Log-in is coming soon.

Share this question

WhatsAppDownload image

Source: official GATE 2026 Session 2 CS question paper and final answer key, organised by IIT Guwahati. Question paper · Answer key

More General Aptitude PYQs

PracticePractise General Aptitude questions →Full paperAll GATE CSE 2026 Session 2 questions →