Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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)}

share|cite|improve this question
When I saw that you had edited I had sort of hoped you would correct the x and y in the first sentence. – Phira May 17 '12 at 8:51
Ah sorry corrected now – lzbrace May 17 '12 at 8:52

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.