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?
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?
Show Hint
- Such a trip is possible for (i), but not for (ii).
- Such a trip is possible for (ii), but not for (i).
- Such a trip is possible for both (i) and (ii).
- Such a trip is possible neither for (i) nor for (ii).
The Correct Option is A
Solution and Explanation
Reframe the problem in graph-theory language: cities are vertices, highways are edges, and the salesperson wants a Hamiltonian cycle, a closed walk that visits every vertex exactly once.
Key test: if any vertex has degree exactly 1, it is a dead end -- the salesperson can reach that city but has no second edge to leave it and continue the tour without retracing the same highway. Any graph containing such a vertex cannot admit a Hamiltonian cycle.
Applying this test to the two highway systems: figure (i) has enough well-distributed connections that a full closed tour through all cities is achievable, so a Hamiltonian cycle exists. Figure (ii) contains a city that is reachable via only one highway, which blocks the formation of any closed tour covering all cities.
Hence the trip described by the salesperson is achievable only for network (i), never for network (ii).
Final answer: option A.
Top Questions on Logical Reasoning
- Pointing to a photograph, a man says, "I have no brothers or sisters, but the father of the person in the photograph is my father’s son." Who is the person in the photograph?
- BITSAT - 2025
- Logical Reasoning
- Logical Reasoning
- In a certain code, "CAT" is written as "DBU." How is "DOG" written in that code?
- BITSAT - 2025
- General Aptitude
- Logical Reasoning
Statement: All flowers are beautiful. Some beautiful things are fragile.
Conclusion I: Some flowers are fragile.
Conclusion II: All beautiful things are flowers.- BITSAT - 2025
- Logical Reasoning
- Logical Reasoning
- For a person, whose monthly salary is Rs 6,000 p.m., how many items are there on which he has to spend more than Rs 1,000 p.m.?
- VITEEE - 2024
- General Aptitude
- Logical Reasoning
- Want to practice more? Try solving extra ecology questions todayView All Questions
Questions Asked in GATE CS exam
A database has 25,000 fixed-length records of 100 bytes (primary key 15 bytes). The data file is block-aligned so each record is fully contained within a block. The file is indexed by a primary index file, also block-aligned and ordered. Block size is 1024 bytes and a block pointer is 5 bytes. Each index entry stores the block’s anchor key (15 bytes) and a pointer (5 bytes). Binary search on an index file of \(b\) blocks needs \(\lceil \log_2 b \rceil\) block accesses in the worst case. Given a key, the number of block accesses required to identify the data file block that may contain the record, in the worst case, is ____________.
- GATE CS - 2023
- Database Management Systems