Nash-Wiliamsova věta
Úloha číslo: 4116
Ukažte, že hrany každého rovinného grafu lze zorientovat tak, že každý vrchol má výstupní stupeň nejvýše 3.
Nápověda
Zvolte libovolnou orientaci a postupně snižujte výstupní stupně vybraných vrcholů tím, že otočíte orientaci podél šikovně vybraných cest.
Řešení
Přepokládejme, že v nějaké orientaci daného grafu \(G\) má vrchol \(u\) výstupní stupeň alespoň čtyři.
Označme symbolem \(S\) množinu vrcholů, do nichž vede orientovaná cesta z \(u\). Platí, že podgraf \(G[S]\) grafu \(G\) indukovaný množinou \(S\) je zároveň podgrafem \(G\) indukovaným hranami, které vycházejí z vrcholů \(S\). Protože \(G\) je rovinný, je rovinný i \(G[S]\). Z Eulerovy formule vyplývá, že \(G[S]\) může mít nejvýše \(3|S|-6\) hran. Proto v \(G[S]\) leží nutně vrchol \(v\), jehož výstupní stupeň je nejvýše 2 – kdyby takový vrchol neexistoval, měl by \(G[S]\) alespoň \(3|S|\) hran.
Otočením hran na cestě z \(u\) do \(v\) získáme graf, v němž se snížil výstupní stupeň \(u\), aniž by výstupní stupeň \(v\) přesáhl hodnotu tři. Výstupní stupně ostatních vrcholů zůstanou nezměněny.
Opakováním uvedeného postupu eliminujeme všechny vrcholy, jejichž výstupní stupeň je alespoň čtyři.
