Problem
COM-B2-M07-P020 Large Independent Set in a Tree
#20
★★★★★ Level 5 of 5
Prove that every tree on \(n\) vertices has an independent set of size at least \(\lceil n/2\rceil\).
Prove that a tree is bipartite, and take the larger part.
A tree has no cycles, hence no odd cycles. Therefore it is bipartite: its vertices can be split into two parts \(A\) and \(B\), with every edge going between the parts.
Inside each part there are no edges, so each part is an independent set. Of the two numbers \(|A|\) and \(|B|\), whose sum is \(n\), one is at least \(\lceil n/2\rceil\). This larger part gives the desired independent set.
Connects trees, bipartiteness, and independent sets.