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

Obtížnost: Snadná úloha (řešená úvahou nebo přímo z definic)
Úloha řešená úvahou
En translation
	Zaslat komentář k úloze