Hranová souvislost kritického grafu
Úloha číslo: 3280
Nechť \(G\) je graf s chromatickým číslem \(k\), takový, že každý jeho vlastní podgraf má barevnost nejvýše \(k-1\). Dokažte, že \(G\) je nutně hranově \((k-1)\)-souvislý.
Řešení
Sporem. Pokud by \(G\) nebyl hranově \((k-1)\)-souvislý, měl by hranový řez velikosti nejvýše \(k-2\) oddělující dvě komponenty \(C\) a \(C’\). Obarvíme obě \(k-1\) barvami.
Sloučením obarvení se může stát, že některá hrana řezu má oba konce stejné barvy \(b\). Protoze je hran řezu méně než barev, lze v komponentě \(C\) najít barvu \(c\) takovou, že žádný vrchol této barvy není incidentní s hranou řezu. Zaměníme-li na \(C\) barvy \(b\) a \(c\), neporušíme obarvení komponenty \(C\), ale snížíme počet hran řezu se stejně obarvenými konci.
Tento proces opakujeme tak dlouho, dokud nedostaneme obarvení grafu \(G\) pomocí \(k-1\) barev, což je kýžený spor.
