Nezávislá množina ve stromě
Úloha číslo: 4078
Dokažte, že každý strom na \(n\) vrcholech má nezávislou množinu velikosti aspoň \(\lceil \frac{n}{2} \rceil\).
Řešení
Každý strom je bipartitní, tedy lze ho obarvit dvěma barvami. Každá třída barevnosti určuje nezávislou množinu. Jedna z těchto dvou tříd obsahuje alespoň polovinu vrcholů.