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 ________.
Show Hint
This is a minimum vertex cover problem on the graph formed by the junctions and walkways; check how many walkways a single guard can cover at most.
Step 1: Translate the picture into a graph. The diagram is a closed loop with five junctions: the top apex, the left-middle junction, the right-middle junction, the bottom-left junction, and the bottom-right junction. The walkways connect apex-to-left, apex-to-right, left-to-bottom-left, bottom-left-to-bottom-right, and right-to-bottom-right. That gives exactly 5 junctions and 5 walkways forming a single closed pentagon-shaped cycle, where every junction touches exactly 2 walkways.
Step 2: Restate the guard requirement in graph terms. A guard placed at a junction can watch every walkway touching that junction. We need every walkway (edge) to have at least one of its two end junctions guarded. This is precisely the definition of a minimum vertex cover of the graph.
Step 3: Show that 2 guards are not enough. Every junction in this cycle touches exactly 2 walkways, so 2 guards can watch at most 2+2=4 walkways even in the best case where the two guarded junctions do not share a walkway. Since there are 5 walkways in total, 2 guards can never cover all of them, so 2 is not sufficient.
Step 4: Show that 3 guards are enough. Place guards at the apex, the bottom-left junction, and the bottom-right junction. The apex covers the two walkways going to the left-middle and right-middle junctions. The bottom-left junction covers the walkway to the left-middle junction and the walkway to the bottom-right junction. The bottom-right junction covers the walkway to the right-middle junction and the walkway to the bottom-left junction. Together, all 5 walkways are covered by just these 3 guarded junctions.
Conclusion: Since 2 guards are provably insufficient and 3 guards achieve full coverage, the minimum number of guards required is 3, which is option 2.
