Independent set
Task number: 4217
Prove that each tree on \( n \) vertices has an independent set of size at least \(\lceil \frac{n}{2} \rceil\).
Solution
Each tree is bipartite, so it can be colored with two colors. Each color class specifies an independent set. One of these two classes contains at least half of the vertices.
