Dlouhý cyklus
Úloha číslo: 3827
Ukažte, že každý \(k\)-souvislý graf na alespoň \(2k\) vrcholech obsahuje cyklus délky alespoň \(2k\).
Nápověda
Využijte větu o vějířích, pokud nejdelší cyklus není dostatečně dlouhý.
Řešení
Je-li \(C\) nejdelší cyklus a jeho délka je menší než \(2k\), potom zvolíme libovolný vrchol \(v\) mimo \(C\). Z Mengerovy věty vyplývá, že mezi \(v\) a \(C\) vede \(k\) vrcholově disjunktních cest z nichž některé dvě vedou do sousedních vrcholů \(C\) (podle Dirichletova principu). Namísto této hrany \(C\) cyklus prodloužíme skrz nalezené cesty a \(v\).