Počet listů v (1,3)-stromu

Kolik nejvíce a nejméně listů může mít strom na \(n\ge 2\) vrcholech, který má stupně pouze 1 a 3?

Řešení
Označme symboly \(l\) počet listů a \(v\) počet vnitřních vrcholů stupně 3.

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.
Odpověď
Strom musí mít sudý počet vrcholů z nichž \(\tfrac{n}2+1\) jsou vždy listy a \(\tfrac{n}2-1\) vnitřní vrcholy.