# Domácí úkol 9.4 - degelim
V úloze pro barvicí algoritmus jsem tvrdil, že při rekonstrukci grafu začneme od vrcholů s nejvyššími stupni. Stejně tak v zadané sekvenci by mělo platit, že $deg(v_i)\geq deg(v_{i+1})$.
Pokud dokážu, že jsou vrcholy skutečně seřazené sestupně (podle stupňů ve finálním grafu) pak věta platit bude, jelikož pro degenerovatelnost bude rozhodující pouze poslední vrchol - ten s nejnižším stupněm.

Mějme tedy nějaký graf, kde přidáme vrchol a přidělíme mu $d$ sousedů. Jeho stupeň bude momentálně roven $d$. Určitě se však musely zvýšit stupně jeho sousedů; byly-li rovny $d$, pak bude nový vrchol mít skutečně nejnižší stupeň a posloupnost vrcholů nebude porušena.
Je možné, že jsme předchozímu vrcholu přidělili méně sousedů? Ano, poté však můžeme posloupnost rekonstrukce obrátit. Zmíněná situace neplatí v řípadě, kdy bylo v grafu málo vrcholů (méně než $d$) - viz níže.

Platí tedy, že zkoumaný vrchol ve chvíli, kdy byl na konci posloupnosti, dostal $d$ sousedů. Totéž platí i pro další vrcholy za ním; jelikož však jejich sousedi museli již existovat v zadané posloupnosti, stupně těchto sousedů se zvýší.