Věta o čtyřech barvách

Úloha číslo: 3641

Dokažte větu o čtyřech barvách pro rovinné grafy bez trojúhelníků.

  • Nápověda

    Nejprve ukažte existenci vrcholu omezeného stupně.

  • Řešení

    Rovinný graf bez trojúhelníků obsahuje vrchol stupně nejvýše tři: kdyby všechny vrcholy měly stupeň alespoň 4, neplatil by odhad \(|E_G|\le2|V_G|-4\).

    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 tři barvy ze čtyřprvkové množiny barev.

Obtížnost: Snadná úloha (řešená úvahou nebo přímo z definic)
Úloha na dokazování, ověřování
En translation
	Zaslat komentář k úloze