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.
A quicker route uses a known graph-theory fact instead of testing coverage by hand: for any cycle graph $C_n$ with $n$ vertices, the minimum vertex cover has size $\lceil n/2 \rceil$.
First confirm the diagram really is a simple cycle: there are 5 junctions and 5 walkways, and tracing the connections (apex to left-middle, left-middle to bottom-left, bottom-left to bottom-right, bottom-right to right-middle, right-middle back to apex) forms one unbroken loop with no shortcuts or extra edges, so this is indeed $C_5$.
Applying the formula with $n=5$: minimum vertex cover $= \lceil 5/2 \rceil = \lceil 2.5 \rceil = 3$.
This can be cross-checked using the complementary idea of a maximum independent set: for an odd cycle $C_n$, the largest set of junctions with no two directly connected has size $\lfloor n/2 \rfloor = 2$. Since vertex cover size plus independent set size equals $n$ for this graph, vertex cover $= 5-2=3$, confirming the same value.
