0
$\begingroup$

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$.

  • 0
    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 connectiviy2013-11-04

1 Answers 1

2

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.

  • 0
    It took me a while to think it through,but I finally got it. Thanks :)2013-01-05