Barevnost duálu
Úloha číslo: 3643
Ukažte, že má-li rovinný graf sudé stupně, pak je barevnost jeho duálu rovna dvěma.
Řešení
Sporem: kdyby duál nebyl dvoubarevný, obsahuje lichý cyklus.
Takový lichý cyklus nemůže ohraničovat stěnu, protože by délka toho cyklu odpovídala stupni příslušného vrcholu a to má být sudé číslo.
Vezměme lichý cyklus \(C\), v jehož vnitřku je co nejmenší počet stěn. Protože nejde o stěnu jedinou, jsou dva vrcholy na \(C\) spojeny cestou \(P\) ležící uvnitř cyklu \(C\). Tato \(P\) rozděluje \(C\) na dva cykly. Jeden z nich je lichý s menším počtem stěn uvnitř, což je spor s volbou \(C\).
Tedy duál neobsahuje žádný lichý cyklus a je proto dvoubarevný.
