Question

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 ________.

• A. 2
• B. 3
• C. 4
• D. 5

Hint:

Treat junctions as vertices and walkways as edges, then find the smallest vertex set touching every edge.

Answer 1

The Correct Option is B

Step 1: Model the picture as a graph.
Each black dot is a vertex (a junction) and each walkway is an edge joining two junctions. Watching a walkway means covering the edge that represents it.

Step 2: Recognize the problem type.
Placing a guard at a junction covers every walkway touching that junction, so we need the smallest set of vertices that touches every edge, which is the minimum vertex cover of the graph.

Step 3: Cover the edges of the house-shaped graph.
The diagram is a five-junction "house" shape: a square base with a triangular roof on top, giving six edges in total. Picking only two junctions between the base and the roof leaves some edges uncovered, so two guards are not enough. Picking three junctions, for example the two bottom corners and the roof apex, touches all six edges between them.

Final Answer:
Three guards, placed at the right junctions, are enough to watch every walkway, and no set of two junctions can do it. \[ \boxed{3} \]