Lesson 3

Theorem (Chvátal (1975); Fisk (1978)). To guard a gallery in the shape of a simple \(n\)-gon, \(\lfloor \frac{n}{3} \rfloor\) guards are sufficient. Moreover, all guards can be placed at vertices of the polygon, or they can all be located strictly inside the polygon.

Proof.

1. Triangulate the polygon. We prove by induction on \(n\) that any simple \(n\)-gon can be triangulated (so that all diagonals lie entirely inside the polygon). Base case \(n=3\) is true. For the inductive step, take a vertex \(v\) with an internal angle less than \(180^{\circ}\) (such a vertex exists because the sum of angles is \(180^{\circ} \cdot (n-2)\)), and its neighbors \(u\) and \(w\). If diagonal \(uw\) lies entirely inside the polygon, draw it and proceed by induction. Otherwise, it intersects some side of the polygon. Move line \(uw\) parallel toward vertex \(v\) until it hits the last vertex \(t\) inside triangle \(uvw\). Then \(vt\) is the desired diagonal.

   

2. Color the triangulation in three colors. We prove by induction on \(n\) that any triangulation is 3-colorable (here, a triangulation is a graph with vertices as polygon vertices, and edges as sides and diagonals). Base case \(n=3\) is clearly true. Inductive step: take any diagonal of the triangulation, which splits the polygon into two independent parts, color each independently by induction, then glue them along the diagonal, ensuring color consistency.
3. Choose the rarest color. In the resulting 3-coloring, one color appears in at most \(\lfloor \frac{n}{3} \rfloor\) vertices. Place guards at these vertices. They can see the entire gallery because it is divided into triangles and each triangle has a vertex of our chosen color.

To ensure guards are not at the vertices, slightly shift each one inward. Specifically, consider the vertex with a guard. They are responsible for viewing all triangles meeting at that vertex. On one side of the vertex there is no triangle (and hence no polygon). So move the guard a bit in the opposite direction (enough to ensure the guard remains inside the polygon).