# for a $k$-edge connected graph there exists edge disjoint paths

As a modification to a previous question I asked

In a $k$-connnected graph for every two paths contain only the initial vertex

I made the following claim and I would like to find out whether it is possible to prove it

If G is a $k$-edge connected graph and $v,v_1,v_2,…,v_k$ are $k+1$ vertices of graph $G$,then for $i=1,2...,k$ there exists a $v−v_i$ path $P_i$ such that each path $P_i$ contains exactly one vertex $v_1,v_2,...v_k$ and for $i$ doesn't equal to $j$ , $P_i$ and $P_j$ are edge disjoint

since a non-trivial graph $G$ is $k$-edge connected if and only if $G$ contains $k$ pairwise edge disjoint u-v paths for each pair u,v of distinct vertices of G but how to show that each path $P_i$ will contain exactly one vertex $v_1,v_2,...v_k$

It is not necessarily that each path $$P_i$$ contains exactly one of $$\{v_1, \cdots, v_k\}$$. A counterexample is as follows.
Counterexample. The following figure shows a $$2$$-edge-connected graph, where $$v$$ is green, $$v_1$$ is blue and $$v_2$$ is red. As you can see, every path from $$v$$ to $$v_2$$ must pass $$v_2$$.
However, it is true that $$P_i$$ and $$P_j$$ are edge-disjoint if $$i \neq j$$. To prove this, you can construct a new graph $$G'$$ by adding a new vertex $$w$$ and $$k$$ new edges, namely $$(w, v_1)$$, $$(w, v_2)$$, $$\cdots$$ and $$(w, v_k)$$, to $$G$$. It is easy to know that $$G'$$ is $$k$$-edge connected. By Menger's theorem, there exists $$k$$ edge-disjoint paths from $$v$$ to $$w$$. If we remove $$w$$ from each of these paths, the paths are from $$v$$ to each $$v_i$$ in $$G$$ and are edge-disjoint.
• But you mean every path from $v$ to $v_2$ must pass $v_1$ Mar 18, 2017 at 18:35
• @Frank That is, every path from $v$ to $v_2$ must contain both $v_1$ and $v_2$. Mar 19, 2017 at 5:15