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.

Obtížnost: Středně těžká úloha
Úloha vyžadující neobvyklý trik nebo nápad
En translation
	Zaslat komentář k úloze