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.