Počet listů v (1,3)-stromu
Úloha číslo: 4077
Mějme strom, který má \(l>0\) listů a \(v\) vnitřních vrcholů, přičemž každý vnitřní vrchol má stupeň 3. Dokažte, že vždy platí \(l = v+2\).
Řešení
Přímo, spočítáme všechny hrany, a vrcholy:
\(|V_G|=l+v\),
\(2|E_G|=l+3v\) (princip sudosti).
Dosazením do \(|V_G|=|E_G|+1\) máme \(l+v =\frac12 (l+3v)+1\), z čehož úpravou dostaneme \(l = v+2\).
Alternativně indukcí podle počtu vnitřních vrcholů.
Pro \(v=0\), \(l=2\) jde o strom \(K_2\) a tvrzení platí.
Vezměme libovolný vrchol stupně tři a rozdělme jej na tři listy. Tím vzniknou tři stromy, splňující indukční předpoklad. Pro \(i=1{,}2,3\) označme \(l_i\) a \(v_i\) počty listů a vnitřních vrcholů v \(i\)-tém vzniklém stromě.
Platí: \(v=v_1+v_2+v_3+1=(l_1-2)+(l_2-2)+(l_3-2)+1=l_1+l_2+l_3-5=l-2\).
První a poslední rovnosti odpovídají situaci, kdy rozdělením vzniknou z jednoho vnitřního vrcholu tři listy.
