# Domácí úkol 9.1 - balgo
Najdeme vrchol s nejnižším stupněm, ($v$) provedeme kontrakce jako v důkazu (nespojení sousedé $x,y$; nový vrchol $w$) a původní vrchol ($v$) uložíme do zásobníku, přičemž si musíme ke každému vrcholu pamatovat i sousedy $x,y$.
Vrcholy stupně 1 můžeme rovnou odstranit (ovšem uložíme je do zásobníku, takže nezmizí).
Vrcholy stupně 0 nemusím řešit, obarvení probíhá pro každou komponentu souvislosti zvlášť.
Tím se nám snížil počet vrcholů, ovšem graf zůstal rovinný, takže určitě existuje v novém grafu vrchol se stupněm $\leq 5$. Zopakujeme postup a uložíme daný vrchol na vršek zásobníku, přičemž přednost budou mít ty vrcholy, které měly nízký stupeň již před kontrakcí.
*To znamená, že později odebraný vrchol budeme obarvovat dříve, tzn. obarvení bude probíhat sestupně podle počtu sousedů (v původním grafu).*
Jakmile nám zbydou osamocené vrcholy, obarvíme je (shodně) a můžeme graf rozbalovat. K vrcholu $w$ připojím $x,y$ (z horní části zásobníku) a hrany z $w$ přepojím do $x,y$ podle toho, jak jsem je zkontrahoval, a zbývající hrany tak patří vrcholu $v$.
Vrcholy $x,y$ obarvíme shodně jako $w$, $w$ nahradíme za $v$ a ten obarvíme zbývající barvou (v době odebrání (a tak i přidání) měl stupeň $\leq 5$, dva sousedi mají stejnou barvu, takže alespoň jedna barva zbyde).
Nyní mohu vrchol $v$ a všechna další data (hrany $vx$, $vy$) odebrat ze zásobníku, takže pracuju s dříve odstraněnými vrcholy. Tím postupně zrekonstruuji původní graf, tentokrát již s obarvenými vrcholy.