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.

Difficulty level: Easy task (using definitions and simple reasoning)
Reasoning task
Cs translation
Send comment on task by email