Vnějškově rovinné grafy
Úloha číslo: 3642
Dokažte větu o třech barvách pro vnějškově rovinné grafy, t.j. pro grafy jež mají rovinné nakreslení takové, že všechny vrcholy leží na vnější stěně.
Nápověda
Nejprve ukažte existenci vrcholu omezeného stupně.
Řešení
Bez újmy na obecnosti můžeme předpokládat, že vnější stěna je ohraničena cyklem a každá vnitřní stěna je trojúhelník – takový graf získáme přidáváním hran do vnějškově rovinného grafu dokud graf zůstává vnějškově rovinný.
Nyní ukážeme, že takový vnějškově rovinný graf obsahuje vrchol stupně nejvýše dva: Přidáním vrcholu do vnější stěny spojeného se všemi ostatními vrcholy dostaneme rovinný graf, v němž jsou všechny stěny trojúhelníky. Tento graf má \(n+1\) vrcholů, \(3n-3\) hran, \(2n-2\) trojúhelníkových stěn a jeden vrchol stupně \(n\). Pokud odebereme přidaný vrchol, zůstane \(n-2\) trojúhelníkových stěn (a jedna \(n\)-úhelníková). Každá hrana na vnější stěně ji musí tuto stěnu oddělovat od nějaké trojúhelníkové stěny. Protože trojúhelníkových stěn je méně než hran na vnější stěně, má některá trojúhelníková stěna společné dvě hrany s vnější stěnou. Tyto dvě hrany určují vrchol stupně dva.
(Alternativní argument, stručnější, ale náročnější na představivost: Podgraf duálu určený vnitřními stěnami je strom. V listech tohoto duálu jsou stěny s vrcholy stupně dva.)
Dále postupujeme indukcí, odebereme takový vrchol, z indukce obarvíme zbytek. Obarvení lze rozšířit i na odebraný vrchol, protože sousedé blokují nejvýše dvě barvy ze tříprvkové množiny barev.
