# k-edge-connected graph problem

Could somebody help to solve this problem:

Prove or disprove: If $G$ is a k-edge-connected graph with nonempty disjoint subsets $S_{1}$ and $S_{2}$ of $V(G)$, then there exist $k$ edge-disjoint paths $P_{1},P_{2},...,P_{k}$ such that $P_{i}$ is a $u_{i}-v_{i}$ path, where $u_{i} \in S_{1}$ and $v_{i} \in S_{2}$, for $i=1,2...,k$, and $|S_{1} \cap V(P_{i})|=|S_{2} \cap V(P_{i})| = 1$.

-
Should be $k$ or $(k-1)$? If there wasn't $(k-1)$ edge disjoint paths, then the graph would be disconnected by removing $(k-1)$ edges selected arbitrary from each path, which is in contrast with the k-edge connectiviy – emab Nov 4 '13 at 2:43

Fix a vertex $u\in S_1$ and $v\in S_2$. Then by Menger's theorem there exists $k$ edge-independent $uv$-paths in $G$.
For each path, $P_i$, if $u$ and $v$ are the only vertices in $S_1$ and $S_2$ then we take $u_i = u$ and $v_i = v$.
Otherwise select any sub-path of $P_i$ connecting a vertex in $S_1$ to a vertex in $S_2$ with no vertices of $S_1$ or $S_2$ in between. The collection of sub-paths are of course edge-independent since the original paths were.