Sign up ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

We have a $K$-connected graph. This graph has non empty disjoint subsets $S_1$ and $S_2$ of $V(G)$. How to show that there exist $k$ internally disjoint paths $P_1, P_2, \ldots, P_K$ such that each path $P_i$ is a $u-v$ path for some $u \in S_1$ and some $v \in S_2$ for $i = 1,2,\ldots,k$ and $|S_1 \cap V(P_i)| = |S_2 \cap V(P_i)| = 1$.

I know there exists $k$ internal paths but how to prove that these paths are disjoint? Any help would be appreciated.

share|cite|improve this question
What is the relevance of S_1, S_2 here ? How are they chosen ? If they're arbitrary, this can not work...Pick $S_1 = V(G) \setminus \{u\}, S_ 2 = \{v\}$ and say $k = 10$. Then you need 10 edges between $u, v$. Is what you're asking just "how do we prove all the $k$ paths beetween $u,v$ are disjoint ? –  Manuel Lafond Nov 17 '13 at 7:11
Let u in S1 and v in S2. Then there exsit k internally disjoint u-v paths in G. I think we can solve it by considering appropriate subpaths of these paths, but could not figure out how? –  user109260 Nov 19 '13 at 2:09

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.