Barevnost kaktusů
Úloha číslo: 4327
Kaktus je zobecnění stromu: souvislý graf, ve kterém každá hrana leží na nejvýše jednom cyklu. (Jinými slovy lze ho vytvořit postupným lepením cyklů a samostatných hran za vrcholy tak, aby nevznikl žádný další cyklus.) Dokažte, že kaktusy mají barevnost nejvýše 3.
Řešení
Budeme postupovat indukcí podle počtu kružnic. Pokud v kaktusu není žádná kružnice, je to strom a ten je dokonce 2-obarvitelný. Indukční krok provedeme takto: vybereme nějakou kružnici \(C\), smažeme její hrany a tím se kaktus rozpadne na komponenty, které jsou opět kaktusy, takže jsou podle indukčního předpokladu 3-obarvitelné. Nyní zvlášť obarvíme kružnici \(C\) (na to stačí 3 barvy) a v každé komponentě permutujeme barvy tak, aby se vrchol, kde je komponenta přilepena na kružnici, barvou shodoval s kružnicí.
