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
Think of each junction as a vertex and each walkway as an edge, and find the smallest set of vertices that touches every edge in this closed 5-sided loop.
Step 1: Turn the picture into a graph problem.
Each junction is a vertex, and each walkway is an edge joining two junctions. Placing a guard at a junction lets that guard watch every walkway touching that junction.
Choosing the smallest set of junctions so that every walkway touches at least one chosen junction is exactly the minimum vertex cover of the graph.
Step 2: Identify the graph.
Label the junctions T (top apex), LU (left upper), RU (right upper), LB (left bottom) and RB (right bottom).
The five walkways are T-LU, T-RU, LU-LB, RU-RB and LB-RB.
Tracing these edges gives a single closed loop T, LU, LB, RB, RU, back to T, so the graph is a cycle with 5 vertices, an odd cycle.
Step 3: Use the rule for covering an odd cycle.
For any cycle with an odd number of vertices n, the minimum vertex cover has size \(\lceil n/2 \rceil\), because picking every alternate vertex always leaves exactly one edge with both ends unchosen when n is odd, so one extra vertex is always needed on top of the "every other vertex" pattern that would work for an even cycle.
Here n = 5, so the minimum vertex cover size is \(\lceil 5/2 \rceil = 3\).
Step 4: Check with an actual choice of guards.
Placing guards at LU, RB and T covers T-LU (by LU or T), T-RU (by T), LU-LB (by LU), RU-RB (by RB) and LB-RB (by RB), so all five walkways are watched with only 3 guards.
No 2-guard placement can work, because 2 vertices touch at most 4 of the 5 edges in this graph, always leaving at least one walkway unwatched.
Final Answer:
The minimum number of guards needed is 3.
\[ \boxed{3} \]
