Věta o vějířích

Úloha číslo: 3826

Dokažte následující zobecnění Mengerovy věty:

  • Varianta

    Graf \(G\) je \(k\)-souvislý právě tehdy, když pro každý jeho vrchol \(v\) a množinu \(A\in{V(G)\choose k}\) existuje \(k\) cest mezi \(v\) a vrcholy množiny \(A\), které jsou vrcholově disjunktní až na vrchol \(v\). (Tyto cesty tvoří „ vějíř“ v grafu \(G\).)

  • Varianta

    Graf \(G\) je \(k\)-souvislý právě tehdy, když pro každé dvě množiny vrcholů \(A,B\in{V(G)\choose k}\) (ne nutně disjunktní) existuje \(k\) vrcholově disjunktních cest, jejichž jeden krajní vrchol leží v \(A\) a druhý v \(B\).

Obtížnost: Středně těžká úloha
Úloha na dokazování, ověřování
En translation
	Zaslat komentář k úloze