Tato úloha neprošla kontrolou správnosti.
Neexistence grafu
Úloha číslo: 3644
Ukažte, že neexistuje eulerovský rovinný graf jehož stěny by tvořil jeden pěticyklus a samé trojúhelníky.
Řešení
Využijeme obarvení stěn bílou a černou barvou takové, že sousední stěny mají různou barvu (vizte předchozí příklad).
Bez újmy na obecnosti předpokládejme, že pětiúhelník je obarvený bíle. Počet hran na hranici černých stěn (samých trojúhelníků) je násobek tří, ale počet hran na hranici bílých stěn je kongruentní 5 \(\pmod 3\).
Tato dvě čísla nemohou být rovna, tedy žádný takový graf neexistuje.