Discussion
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?
Answer: A
Such a trip is possible for (i), but not for (ii).
The trip is a Hamiltonian cycle: a closed route through every city exactly once.
In (i), a 4 by 4 grid of 16 cities, such a cycle exists. Number rows 1 to 4 from the top and columns 1 to 4 from the left. One route: along row 1 from column 1 to column 4; down to row 2 and left to column 2; down to row 3 and right to column 4; down to row 4 and left to column 1; then up column 1 through rows 3 and 2 back to the start. It passes through all 16 cities once.
In (ii) there are five cities. Three of them have only two highways each, and a cycle through a city of degree two must use both of its highways. Those forced highways already include three edges at the top-left city (to the top-right city, the middle city and the left city). A cycle can use only two edges at any city, so no Hamiltonian cycle exists. That rules out the options claiming a trip for (ii) and the one denying it for (i).
Post your comment
Please log in or register to post a comment.
Examination Categories
- SSC Exams
- Banking Exams
- Teaching Exams
- Civil Services Exams
- Railways Exams
- Engineering Recruitment Exams
- Defence Exams
- State Government Exams
- Police Exams
- Insurance Exams
- Nursing Exams
- Other Government Exams
- NRA CET
- PG Entrance Exams
- Campus Placement
- MBA Entrance Exams
- CUET and UG Entrance
- Judiciary Exams
- Regulatory Body Exams
- Software Development