# Graph problem

• Dec 26th 2012, 12:48 PM
Franek222
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
• Dec 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 \$\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.