Počet listů
Úloha číslo: 4076
Dokažte, že pokud v konečném stromu existuje vrchol stupně \(k\), tak potom strom má alespoň \(k\) listů.
Řešení
Pro \(k\le 1\) tvrzení platí, uvažujme proto \(k\ge 2\) a vrchol \(v\) tohoto stupně.
Opakujeme \(k\) krát následující operaci. Odebráním hrany od \(v\) vzniknou dvě komponenty. Jedna tato komponenta neobsahuje \(v\). Tato komponenta je strom, tedy buď je to jeden vrchol, který sám o sobě byl listem před odebráním hrany nebo tento strom má nějaké hrany a v tomto případě obsahuje alespoň dva listy. Nejvýše jeden z těchto listů mohl být sousedem \(v\), ostatní byly listy i před odebráním hrany.
Za každou odebranou hranu jsme našli alespoň jeden list, strom tedy musí mít alespoň \(k\) listů.
