2
$\begingroup$

Define $\kappa(u, v)$ as the minimum vertex cut for u and v, $\lambda(u, v)$ as the minimum edge cut for u and v

Let $u$ and $v$ be nonadjacent vertices of a connected graph $G$. Prove or disprove the following: Every set of $\kappa(u, v)$ internally disjoint $u - v$ paths in $G$ is contained in a set of $\lambda(u, v)$ edge-disjoint $u - v$ paths.

I'm working through the questions of applied and algorithmic graph theory, this is one of the questions in the networks chapter

I think the answer is true, but spent a lot of time on this and can't figure out how to prove it

[EDIT] Found a counter-example let the graph be the set of edges {(u,a),(a,b),(b,c),(c,v),(u,b),(a,c),(c,d),(d,v)} then $\kappa(u,v)=1$, $\lambda(u,v)=2$ and let the set of internally disjoint paths be {(u,a,b,c,v)}

  • 0
    Ah sorry corrected now2012-05-17

0 Answers 0