Take the 2-minute tour ×
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.

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|improve this question
    
If this is homework, please consider adding the homework tag. –  Aryabhata Oct 19 '10 at 13:27
    
Yeah, added already. –  luocreeks Oct 19 '10 at 15:58
    
What have you done to get started? –  Code-Guru Dec 18 '12 at 3:32

2 Answers 2

Hint:

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

share|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:

http://www.iis.sinica.edu.tw/page/jise/2001/200103_02.pdf

share|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

 
discard

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.