## 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.