Vrcholy na společném cyklu
Úloha číslo: 3823
Dokažte následující tvrzení: Nechť \(G\) je (vrcholově) 2-souvislý graf a \(u\), \(v\) dva jeho vrcholy. Potom existuje kružnice v \(G\) obsahující \(u\) i \(v\).
Nápověda
Použijte ušaté lemma nebo jednu z Mengerových vět.
Řešení
Indukcí podle přidávání uší.
Tvrzení zřejmě platí pro cyklus.
Je-li \(U\) ucho a tvrzení platí pro \(G-U\), potom je třeba rozebrat případy podle pozice \(u\) a \(v\) vzhledem k \(U\):
Pokud \(u,v\notin U\), potom cyklus najdeme podle indukčního předpokladu.
Pokud \(u,v\in U\), potom najdeme cyklus \(C\) v \(G-U\) obsahující koncové vrcholy \(x,y\) ucha \(U\). Z tohoto cyklu zvolíme jednu z cest mezi \(x\) a \(y\) a doplníme ji s \(U\) na hledaný cyklus.
Pokud \(u\in U\) a \(v\notin U\), pak nejprve nalezneme cyklus \(C\) v \(G-U\) procházející \(x\) a \(v\) a také nějakou cestu z \(y\) do libovolného vrcholu \(C\) různého od \(x\). V tomto podgrafu již nalezneme hledaný cyklus.
Mengerova věta dá argument snáz: vrcholově disjunktní cesty přímo složíme na cyklus.