2
$\begingroup$

If 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?

  • 0
    What have you done to get started?2012-12-18

2 Answers 2

1

Hint:

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

  • 0
    Yes! I've known how to prove it. Thanks a lot!2010-10-20
0

Perhaps this paper might be of use:

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

  • 0
    Thank you all the same. But there is no proof in this paper. It has only mentioned this conclusion.2010-10-19