# Graph problem

• December 26th 2012, 12:48 PM
Franek222
Graph problem
I have big problem to solve, could someone help :)

Prove or disprove: If $G$ is a k-edge-connected graph and $v,v_{1},v_{2},...,v_{k}$ are $k+1$ distinct vertices of $G$ then for $i = 1,2,...k$ there exist $v-v_{i}$ paths $P_{i}$ such that each path $P_{i}$ contains exactly one vertex of ${v,v_{1},v_{2},...,v_{k}}$, namely $v_{i}$, and for $i \neq j, P_{i}$ and $P_{j}$ are edge-disjoint
• December 26th 2012, 02:05 PM
Plato
Re: Graph problem
Quote:

Originally Posted by Franek222
I have big problem to solve, could someone help :)
Prove or disprove: If $G$ is a k-edge-connected graph and $v,v_{1},v_{2},...,v_{k}$ are $k+1$ distinct vertices of $G$ then for $i = 1,2,...k$ there exist $v-v_{i}$ paths $P_{i}$ such that each path $P_{i}$ contains exactly one vertex of ${v,v_{1},v_{2},...,v_{k}}$, namely $v_{i}$, and for $i \neq j, P_{i}$ and $P_{j}$ are edge-disjoint

I find this description hard to follow.
However, you may find this webpage useful.

Note that the degree of any vertex is $\ge k$. That gives some bound on the number of edges.