GATE 2026 IN – Question 3
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 ________.
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: (B) 3
Explanation
The walkways form a cycle with five vertices and five edges. A guard at a vertex watches its two incident edges.
Two guards cover at most four edges, so they cannot cover all five walkways. Three guards suffice: place one at the top vertex and one at each bottom vertex. The top guard covers the two sloping edges, and the bottom guards cover the two vertical edges and the bottom edge.
The minimum is therefore **3 guards (B)**.