Kružnice v k-souvislém grafu.

Úloha číslo: 3828

Dokažte, že v každém \(k\)-souvislém grafu leží libovolných \(k\) vrcholů na společné kružnici.

  • Nápověda

    Postupujte sporem a předpokládejte existenci cest podle Mengerovy věty.

  • Řešení

    Nechť \(S\) je daná množina a \(C\) je kružnice s nejvíce vrcholy z \(S\).

    Předpokládejme pro spor existenci \(v\in S\setminus C\). Podle Mengerovy věty existuje mezi \(v\) a \(C\) alespoň \(k\) disjunktních cest.

    Koncové vrcholy těchto cest dělí \(C\) na \(k\) úseků. Podle Dirichletova principu, alespoň jeden úsek neobsahuje ve svém vnitřku žádný vrchol z \(S\), tedy lze tento úsek nahradit příslušnými dvěma cestami vedoucími do \(v\).

    Tím získáme kružnici s více vrcholy z \(S\), než měla \(C\), což je hledaný spor.

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