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\).

Obtížnost: Obtížná úloha
Úloha řešená úvahou
Úloha vyžadující neobvyklý trik nebo nápad
En translation
	Zaslat komentář k úloze