Lesson 5

The first useful fact says that a circulation cannot cross a cut with a nonzero total amount.

Lemma. Let \(\phi\) be a circulation in a directed graph \(G=(V,E)\), and let \(S\subseteq V\). Then \[\sum_{e\in\delta^-(S)}\phi(e)=\sum_{e\in\delta^+(S)}\phi(e) \ ,\] where \(\delta^{+}(S)\) is the set of edges leaving \(S\), and \(\delta^{-}(S)\) is the set of edges entering \(S\).

Proof. Sum the conservation equalities over all vertices of \(S\). Every edge with both ends in \(S\) appears once on the left and once on the right, so these internal contributions cancel. The only terms that remain are exactly the edges crossing the cut.◼