Take the 2-minute tour ×

Suppose we have an oriented graph and max-flow has been determined.

I found that to determine min-cut or minimum s-t cut can then be found by labeling graph nodes such that nodes belonging to source are those which can be reached from source by unsaturated edges. On the contrary: Nodes belonging to sink are all the other, i.e. nodes reachable from sink by saturated edges.

My question is - why? I am unable to grasp this "phenomenon" intuitively.

In other words: Why the minimum cut cannot go through any other egdes, but those who connect nodes label as "belonging to the source" and those "belonging to the sink". Why the min-cut does not go through any other nodes?

share|improve this question
@Garry Myerson Shame on me... I forgot to accept most of them. –  Libor Sep 18 '12 at 14:03

1 Answer 1

up vote 2 down vote accepted

I will try to show you why this is intuitive using counter example. Let us call the set reachable by unsaturated paths A, and the other set B. so s is in A, and t is in B. We know that by definition, each edge from A to B is in the minimum cut. Now suppose A were some other set such that it had a node v such that v was not reachable by an unsaturated path. This means that there is an edge such that the path from s to v is saturated, and let its capacity be x and its endpoints be x1 and x2. Also, let the minimum capacity of the edge from v to B be y. If we move x2 to B, and all vertices on x2-v path to B, then we will have a more minimal cut than earlier, since the capacity of our cut is now reduced by y and increased by x (y-x>=0). Therefore it couldnt have been a minimum cut in the first place. The other case is that some edge from A to B is not saturated. This implies that there is a node in B which is reachable from A by an augmenting path, which again leads to a contradiction.

share|improve this answer
Thanks for explanation. I overlooked the fact that flow cannot be manipulated on individual edges - it can be decreased on whole path only, thus making it an augmenting path again. –  Libor Sep 18 '12 at 14:02

Your Answer


