Tvrzení o společných cyklech

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.
Řešení
Uvedené tvrzení neplatí ani pro tři vrcholy – stačí vzít úplný bipartitní graf \(K_{2{,}3}\) a trojici vrcholů z větší partity.

Tento graf je (vrcholově) dvousouvislý, ale všechny kružnice jsou čtyřcykly, tedy žádný neobsahuje všechny tři zvolené 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\).
Řešení
Odebráním \(n\) zůstane graf dvousouvislý, v něm stačí najít kružnici procházející \(y\), což už je snadné (dokonce každá dvojice vrcholů leží na společném cyklu).
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\).
Řešení
Tvrzení neplatí. Protipříkladem je graf \(K_{2{,}3}\). Vrcholy stupně 2 by v orientaci musely mít jednu hranu vcházející a jednu vycházející. Potom z těchto tří lze zvolit za \(u\) a \(v\) takové, že z nich vedou hrany do stejného vrcholu. Kružnice určená \(u\) a \(v\) je pak dána jednoznačně a nebude jednosměrně orientovaná.