Statement

Lemma

Let be a flow network with a flow and an st-cut . Then the flow across is equal to the

Proof

We prove by induction on the size of .

If then then is easy to calculate.

This gives the desired result.

Suppose now and we have shown the result for st-cuts with smaller .

As there is an element with (note as ). Therefore consider the altered st-cut .

By the conservation of flow we have

giving

As by induction we have

giving the desired result for .

So by induction we have the result holds in general.