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

s and t are two nodes in a graph. How to prove that the maximum number of edge-disjoint cut sets which divide s and t equals the length of the shortest path from s to t?

share|cite|improve this question
What have you done to get started? – Code-Guru Dec 18 '12 at 3:32


First show that the size of any collection of edge-disjoint cut-sets cannot exceed the length of the shortest path.

share|cite|improve this answer
Yes! I've known how to prove it. Thanks a lot! – luocreeks Oct 20 '10 at 5:27

Perhaps this paper might be of use:

share|cite|improve this answer
Thank you all the same. But there is no proof in this paper. It has only mentioned this conclusion. – luocreeks Oct 19 '10 at 15:57

Your Answer


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

Not the answer you're looking for? Browse other questions tagged or ask your own question.