1. ## Graph problem

I have big problem to solve, could someone help

Prove or disprove: If $\displaystyle G$ is a k-edge-connected graph and $\displaystyle v,v_{1},v_{2},...,v_{k}$ are $\displaystyle k+1$ distinct vertices of $\displaystyle G$ then for $\displaystyle i = 1,2,...k$ there exist $\displaystyle v-v_{i}$ paths $\displaystyle P_{i}$ such that each path $\displaystyle P_{i}$ contains exactly one vertex of $\displaystyle {v,v_{1},v_{2},...,v_{k}}$, namely $\displaystyle v_{i}$, and for $\displaystyle i \neq j, P_{i}$ and $\displaystyle P_{j}$ are edge-disjoint

2. ## Re: Graph problem

Originally Posted by Franek222
I have big problem to solve, could someone help
Prove or disprove: If $\displaystyle G$ is a k-edge-connected graph and $\displaystyle v,v_{1},v_{2},...,v_{k}$ are $\displaystyle k+1$ distinct vertices of $\displaystyle G$ then for $\displaystyle i = 1,2,...k$ there exist $\displaystyle v-v_{i}$ paths $\displaystyle P_{i}$ such that each path $\displaystyle P_{i}$ contains exactly one vertex of $\displaystyle {v,v_{1},v_{2},...,v_{k}}$, namely $\displaystyle v_{i}$, and for $\displaystyle i \neq j, P_{i}$ and $\displaystyle 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 $\displaystyle \ge k$. That gives some bound on the number of edges.