Tvrzení o společných cyklech
Úloha číslo: 3825
Dokažte nebo vyvraťte následující tvrzení:
Varianta
Nechť \(G\) je vrcholově 2-souvislý graf a \(u, v, w, z\) čtyři jeho vrcholy. Potom existuje kružnice v \(G\) obsahující všechny tyto vrcholy.
Varianta
Nechť \(G\) je vrcholově 3-souvislý graf a \(y, n\) dva jeho vrcholy. Potom existuje kružnice v \(G\) procházející vrcholem \(y\) a neprocházející vrcholem \(n\).
Varianta
Každý vrcholově 2-souvislý graf \(G\) má orientaci hran takovou, že pro libovolné dva vrcholy \(u\) a \(v\) existuje v \(G\) jednosměrně orientovaná kružnice taková, že obsahuje \(u\) i \(v\).