Skóre stromu
Úloha číslo: 4075
Mějme posloupnost čísel \(1\le d_1\le d_2 \le … \le d_n\) takovou, že \(\sum\limits_{i=1}^{n} d_i = 2n-2\). Dokažte, že \((d_1,…,d_n)\) je skóre stromu.
Řešení
Indukcí podle počtu vrcholů:
Pro \(n=2\) je \((d_1,d_2)=(1{,}1)\) a hledaný strom je \(K_2\).
Pro \(n\ge 3\) platí, že \(d_1=1\), jinak by byl součet alespoň \(2n\). Také platí \(d_n>1\), protože jinak by byl součet \(n\).
Posloupnost \((d_2,d_3,…,d_n-1)\) má součet \(2(n-1)-2\), tedy je podle indukčního předpokladu po případném přerovnání skóre stromu. Přidáním nového souseda k vrcholu stupně \(d_n-1\) dostaneme hledaný strom.
