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
Treat junctions as vertices and walkways as edges, then find the smallest vertex set touching every edge.
This is a minimum vertex cover problem in disguise: each guard sits on a junction and automatically watches every walkway meeting there, so we need the fewest junctions that together touch every line segment in the figure.
Option (A), 2: two junctions can touch at most four walkways between them here, so at least one walkway is left unwatched. Not enough.
Option (B), 3: a careful choice of three junctions, one from each cluster of the house-shaped graph, touches every walkway shown. This works.
Option (C), 4: four guards also work, but the question asks for the minimum, and three already suffice, so four is not the best answer.
Option (D), 5: placing a guard at every junction obviously watches all walkways, but it is far from minimal.
Since three junctions are enough and two are not, the minimum number of guards needed is $3$, option (B).
