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.