Consider an art gallery whose walkways are shown as lines in the diagram. A black dot represents a junction of two walkways. A guard may be placed at a junction to watch over the walkways that join at that junction. The minimum number of guards needed to watch all the walkways is ________.
Figure Q.3 — walkway network of the art gallery
Options:
(A) 2
(B) 3
(C) 4
(D) 5
Official Answer Key:
B
Step-by-Step Solution & Explanation
The figure is a closed loop through 5 junctions and 5 walkways, i.e. a cycle graph C₅.
A guard at a junction watches only the walkways meeting at that junction, so the problem is the minimum vertex cover of C₅.
For a cycle with n vertices, minimum vertex cover = ⌈n/2⌉ = ⌈5/2⌉ = 3.
Verification that 2 is impossible: two junctions touch at most 2 + 2 = 4 walkway-ends distinct edges — at best 4 of the 5 walkways — leaving one unwatched.
Practice This in Real CBT Exam Interface
Test yourself with the official TCS-iON palette, virtual calculator, and immediate performance analytics.