I'm interested in finding out some real-life applications of the art gallery theorem:
$\lfloor n/3\rfloor$ guards are always sufficient and sometimes necessary to guard a simple polygon with n vertices.
[Math] What are some practical applications of art gallery theorem
graph theory
Related Solutions
If the tree has $m$ vertices of degree $k$ and $n-m$ vertices of degree $1$, then by the Handshakking lemma
$$km+(n-m) =\sum \mbox{degree} = 2 \mbox{ no edges} = 2n-2 $$
This proves that
$$(k-1)m=n-2$$
thus $k-1$ must divide $n-2$.
You also need to prove that if this is the case, it is possible to build such a tree....But this is easy.
For every polygon with at most 5 edges there is a triangulation where all diagonals meet in a single point $v$. This point is a visibility center, since every triangle can be seen from it.
In this triangulation every triangle has positive area. Hence we can perturb $v$ in any direction such that we still have a triangulation. If we perturb towards the polygon then the new point lies in the visibility kernel.
We can discuss this right away for the general $n$-gon setting. Also the classical approach goes via a triangulation argument. Here, every guard is responsible for an area formed by a "fan" of triangles. Again we can perturb the triangulation and add the perturb point. Then we add 2 new triangles to the perturbed triangulation and observe, that the perturbed point can see all of the "fan". This is not super-formal. But the idea should be clear.
Best Answer
From the book: How to Guard an Art Gallery and Other Discrete Mathematical Adventures by T.S. Michael:
The zookeeper problem is related to the art gallery theorem but is not the same. Here we are seeking a path of minimum length which meets the boundary of each cage without going within any cage. There are several other such problems (fortress problem, prison yard problem). Many of these problems have been solved by using Chvatal's inductive approach of the original art gallery theorem.