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.

Obtížnost: Snadná úloha (řešená úvahou nebo přímo z definic)
Úloha na dokazování, ověřování
En translation
	Zaslat komentář k úloze