Obarvení stromu
Úloha číslo: 4421
Řešení
Žvolme nějaký vrchol stromu \(r\) a rozdělme vrcholy do hladin podle vzdálenosti od \(r\). Postupně každou hladinu obarvíme: jakmile budeme chtít obarvit vrcholy na hladině \(i\), máme obarvené právě vrcholy na hladinách \(j < i\).
Na hladině \(0\) je pouze vrchol \(r\). Pro ten máme právě \(k\) možností, jak pro něj zvolit barvu, čímž vyřešíme hladinu \(0\).
Nyní chceme obarvit každou zbylou hladinu \(i > 0\). Jelikož máme strom, existuje právě jedna cesta z libovolného \(v\) do \(r\). Tudíž každý vrchol \(v\) na hladině \(i\) je spojen právě s jedním vrcholem \(u\) na hladině \(i-1\), který má již zvolenou barvu \(c\). Můžeme tedy \(v\) obarvit libovolnou jinou barvou, což pro něj dává \(k-1\) možností.
Jiný způsob, jak dojít k témuž výsledku, je indukcí pomocí odtrhavání listů.
Výsledek
\[k \cdot (k-1)^{n-1}\]
