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?
Tap to open full sizeFigure description
Two graphs. Figure (i) is a 4 by 4 square grid of 16 black dots (cities), 4 rows and 4 columns, with a line segment joining each pair of horizontally adjacent dots and each pair of vertically adjacent dots (24 edges). Figure (ii) has 5 dots: A at top-left, B at top-right, C at the right-middle inside the shape, D at the left-lower side, E at the bottom. Line segments: A-B (top horizontal), A-C, A-D, B-E, C-E, D-E. So A and E each connect to B, C and D, and there are no other edges.
- (A)
Such a trip is possible for (i), but not for (ii).
- (B)
Such a trip is possible for (ii), but not for (i).
- (C)
Such a trip is possible for both (i) and (ii).
- (D)
Such a trip is possible neither for (i) nor for (ii).