Lesson 6

Lemma. In a directed unweighted graph \(G\), there are \(k\) edge-disjoint paths from \(s\) to \(t\) if and only if the flow from \(s\) to \(t\) in the network obtained from \(G\) by adding unit capacities is at least \(k\).

Proof. In one direction it's quite simple: if there are \(k\) edge-disjoint paths, then one unit of flow can go through each. Let's deal with the reverse direction.

Take a maximum flow (of size at least \(k\)) and assume without loss of generality that it is integral (for example, our algorithm constructs only integral flows for networks with integer capacities). We want to show that from this flow we can extract \(k\) edge-disjoint paths. We proceed by induction on the number of edges carrying flow.

Start from vertex \(s\) and follow edges (of unit capacity) carrying one unit of flow. If we eventually reach \(t\), we simply decrease the flow by one along the found path and continue by induction. Otherwise, we reach a vertex we've already seen. Then a cycle is formed, carrying one unit of flow. This cycle's flow can be zeroed, and we again apply the inductive hypothesis.◼