The max-flow min-cut theorem

Theorem

The max-flow min-cut theorem

T-111Home MU-307Threads structure · number

Statement

Let \(G=(V,E)\) be a finite directed graph with a capacity function \(c:E\to\mathbb{R}_{\geq 0}\), and let \(s,t\in V\) with \(s\neq t\) be designated source and sink vertices. A flow is a function \(f:E\to\mathbb{R}_{\geq 0}\) satisfying the capacity constraint \(0\le f(e)\le c(e)\) for every \(e\in E\) and conservation at every vertex \(v\in V\setminus\{s,t\}\): \(\sum_{e\ \text{into}\ v} f(e) = \sum_{e\ \text{out of}\ v} f(e)\). The value of \(f\) is \(|f| = \sum_{e\ \text{out of}\ s} f(e) - \sum_{e\ \text{into}\ s} f(e)\). An \((s,t)\)-cut is a partition \(V = S \sqcup T\) with \(s\in S\), \(t\in T\); its capacity is \(c(S,T) = \sum_{e=(u,v)\in E,\ u\in S,\ v\in T} c(e)\). Then \(\max_f |f| = \min_{(S,T)} c(S,T)\), the maximum taken over feasible flows and the minimum over \((s,t)\)-cuts.

Why it matters

This is the founding duality theorem of network optimisation: it converts a question about the best way to route something (a maximisation over an exponentially large, continuous space of flows) into a question about the worst bottleneck (a minimisation over cuts). Neither side is obviously easy to compute in isolation, yet the theorem guarantees they coincide, and this coincidence is what makes max-flow algorithms simultaneously algorithms for finding provably minimum bottlenecks — a certificate of optimality comes for free.

Its reach goes far beyond literal pipe networks: bipartite matching (via Hall's theorem and König's theorem), vertex/edge connectivity (Menger's theorem), project scheduling, image segmentation, and baseball elimination all reduce to instances of max-flow, and in each case the min-cut side of the theorem is what supplies the structural insight — a minimum vertex cover, a minimum separating set, a minimum set of games that must go a certain way.

Hypotheses

Finite graph \((V,E)\).On an infinite network (Ford & Fulkerson's classical "infinite ladder" example) the supremum of flow values can exceed every cut capacity's infimum, or a maximising flow may fail to exist at all — the compactness argument in the proof needs a finite-dimensional flow polytope.

Capacities are finite and non-negative, \(0\le c(e)\lt\infty\).Negative capacity would let an edge carry flow "against itself" cheaper than not using it at all, and the weak-duality step \(f(S,T)\le c(S,T)\) — which needs \(f(e)\ge0\) on backward-crossing edges to be discarded, not added — collapses; infinite capacity on a crossing edge would make every cut through it have infinite capacity, degenerating the minimisation.

\(s\neq t\).If \(s=t\) no partition with \(s\in S,\,t\in T\) exists, so "cut" is undefined and the statement is vacuous; the theorem is only meaningful for a genuine source-to-sink question.

Conservation holds at every internal vertex (no storage or leakage).If a vertex were allowed to absorb or emit flow (violate conservation), the value of \(f\) measured at \(s\) would no longer equal the net flow crossing an arbitrary cut \((S,T)\) — the key lemma \(f(S,T)=|f|\) is proved by telescoping the conservation identities over \(S\setminus\{s\}\), and that telescoping sum only collapses correctly when every internal vertex truly conserves flow.

Proof

\text{For any flow } f \text{ and any } (s,t)\text{-cut } (S,T),\qquad f(S,T) := \sum_{u\in S,\,v\in T,\,(u,v)\in E} f(u,v) \;-\; \sum_{u\in S,\,v\in T,\,(v,u)\in E} f(v,u) \;=\; |f|.

Definition of net flow across a cut, to be established in the next step. A

|f| = \sum_{v\in S}\Bigl(\sum_{e\ \text{out of}\ v} f(e) - \sum_{e\ \text{into}\ v} f(e)\Bigr)

By the conservation hypothesis, every summand for \(v\in S\setminus\{s\}\) is exactly \(0\), so the sum over all \(v\in S\) equals the single non-zero term at \(v=s\), which is \(|f|\) by definition. This is a telescoping/regrouping identity, legal because \(S\) is a finite set and the double sum \(\sum_{v\in S}\sum_{e\text{ at } v} f(e)\) can be reorganised by which endpoint(s) of each edge \(e\) lie in \(S\). B

\sum_{v\in S}\Bigl(\sum_{e\ \text{out of}\ v} f(e) - \sum_{e\ \text{into}\ v} f(e)\Bigr) = f(S,T)

Classify each edge \(e=(u,v)\) by the location of \(u,v\) relative to \(S\): an edge with both endpoints in \(S\) contributes \(+f(e)\) once (as "out of \(u\)") and \(-f(e)\) once (as "into \(v\)"), cancelling; an edge \(S\to T\) contributes \(+f(e)\) once and \(0\) from the \(T\) side (not summed); an edge \(T\to S\) contributes \(-f(e)\) once. Summing over all edges recovers exactly \(f(S,T)\) as defined in Step 1. Combined with Step 2 this proves the cut-value lemma \(f(S,T)=|f|\) for every flow and every cut. B

f(S,T) = \sum_{S\to T} f(e) - \sum_{T\to S} f(e) \;\le\; \sum_{S\to T} f(e) \;\le\; \sum_{S\to T} c(e) = c(S,T)

The subtracted sum is \(\ge 0\) since \(f\ge 0\) (drop it, first inequality); each remaining term satisfies \(f(e)\le c(e)\) by the capacity constraint (second inequality). This is weak duality: for every flow \(f\) and every cut \((S,T)\), \(|f| = f(S,T) \le c(S,T)\). A

\max_f |f| \;\le\; \min_{(S,T)} c(S,T)

Step 4 holds for every pair \((f,(S,T))\) independently, so it holds in particular for a flow maximising \(|f|\) against a cut minimising \(c(S,T)\); taking max on the left and min on the right of a universally quantified inequality preserves it. This gives one direction; equality is the substance still to prove. A

\text{The set of feasible flows } \mathcal{F} = \{f\in\mathbb{R}^E : 0\le f(e)\le c(e)\ \forall e,\ \text{conservation at } V\setminus\{s,t\}\} \text{ is non-empty, closed and bounded.}

\(\mathcal{F}\) is non-empty (the zero flow \(f\equiv 0\) is feasible); it is bounded because \(\mathcal{F}\subseteq \prod_{e\in E}[0,c(e)]\), a product of finite closed intervals (using finiteness of \(E\) and of every \(c(e)\)); it is closed because it is cut out of \(\mathbb{R}^E\) by finitely many non-strict linear (in)equalities, each of which defines a closed set, and a finite intersection of closed sets is closed. C

\exists\, f^{\ast}\in\mathcal{F} \text{ with } |f^{\ast}| = \max_{f\in\mathcal{F}} |f|.

\(|\cdot|:\mathbb{R}^E\to\mathbb{R}\) is a continuous (linear) function of \(f\), and \(\mathcal{F}\) is a non-empty compact subset of \(\mathbb{R}^E\) (closed and bounded in finite dimension, Step 6, invoking the Heine–Borel theorem). By the extreme value theorem a continuous function on a non-empty compact set attains its supremum. This is the step that genuinely needs finiteness of \(V\), \(E\) and the capacities — it can fail on infinite networks. C

\text{Fix a maximum flow } f^{\ast}. \text{ Define the residual graph } G_{f^{\ast}}=(V,E_r): \text{ for } e=(u,v)\in E, \text{ include } (u,v)\in E_r \text{ with residual capacity } c(e)-f^{\ast}(e) \text{ if this is } \gt 0, \text{ and include } (v,u)\in E_r \text{ with residual capacity } f^{\ast}(e) \text{ if this is } \gt 0.

Standard definition (Ford–Fulkerson): a residual edge records how much more flow could still be pushed forward along \(e\), or how much could be cancelled by pushing backward along \(e\). A

\text{There is no directed path from } s \text{ to } t \text{ in } G_{f^{\ast}}.

Suppose such an augmenting path \(P\) existed, with residual capacities \(r(e_1),\dots,r(e_k)\gt 0\) along its edges. Let \(\delta = \min_i r(e_i) \gt 0\) (finite minimum of a finite non-empty set of positive numbers, well-defined since \(E\), hence \(P\), is finite). Increase \(f^{\ast}\) by \(\delta\) along each forward-type edge of \(P\) and decrease it by \(\delta\) along each backward-type edge of \(P\); the result \(f'\) still satisfies \(0\le f'(e)\le c(e)\) (by choice of \(\delta\) as the bottleneck) and still conserves flow at every internal vertex of \(P\) other than \(s,t\) (the \(+\delta\) in equals the \(+\delta\) out), so \(f'\) is feasible with \(|f'| = |f^{\ast}| + \delta \gt |f^{\ast}|\), contradicting maximality of \(f^{\ast}\) from Step 7. This is the key idea of the whole proof. B

\text{Let } S = \{v\in V : \text{there is a directed path from } s \text{ to } v \text{ in } G_{f^{\ast}}\}, \quad T = V\setminus S.

\(s\in S\) trivially (the empty path); \(t\notin S\) by Step 9, so \(t\in T\); hence \((S,T)\) is a genuine \((s,t)\)-cut. A

\text{For every } e=(u,v)\in E \text{ with } u\in S, v\in T:\ f^{\ast}(e)=c(e). \qquad \text{For every } e=(u,v)\in E \text{ with } u\in T, v\in S:\ f^{\ast}(e)=0.

If the first equality failed then \(c(e)-f^{\ast}(e)\gt 0\), so \((u,v)\in E_r\); since \(u\in S\) is reachable from \(s\), so would \(v\) be, contradicting \(v\in T\). If the second failed then \(f^{\ast}(e)\gt 0\), so the reverse residual edge \((v,u)\in E_r\); since \(v\in S\)... more precisely here \(u\in T, v\in S\), so \(f^{\ast}(u,v)\gt0\) gives residual edge \((v,u)\), and since \(v \in S\) is reachable, and this residual edge goes from \(v\) to \(u\), it would put \(u\) in \(S\), contradicting \(u\in T\). Both contradict the definition of \(S\) in Step 10. B

f^{\ast}(S,T) = \sum_{S\to T} f^{\ast}(e) - \sum_{T\to S} f^{\ast}(e) = \sum_{S\to T} c(e) - 0 = c(S,T).

Substitute the two equalities of Step 11 into the definition of \(f^{\ast}(S,T)\) from Step 1. A

|f^{\ast}| = f^{\ast}(S,T) = c(S,T) \;\ge\; \min_{(S',T')} c(S',T') \;\ge\; \max_f |f| \;\ge\; |f^{\ast}|,

First equality by the cut-value lemma (Steps 1–3) applied to \(f^{\ast}\); second by Step 12; the two middle inequalities are, respectively, that \(c(S,T)\) is one particular cut capacity hence at least the minimum, and weak duality (Step 5); the last is because \(f^{\ast}\) is itself a feasible flow. All quantities are therefore forced to be equal: \(\max_f|f| = |f^{\ast}| = c(S,T) = \min_{(S',T')} c(S',T')\), which is the theorem. B

Result

\max_{f} |f| \;=\; \min_{(S,T)} c(S,T)

Reading. The largest amount of flow that can be pushed from source to sink through a capacitated network exactly equals the smallest total capacity of any set of edges whose removal disconnects the source from the sink. Every maximum flow saturates every edge crossing every minimum cut, and every minimum cut is "tight" against the maximum flow's value.

Scope. Applies to any finite directed network with finite non-negative real edge capacities, a single designated source and sink with \(s\neq t\), and flows required to conserve at internal vertices. It extends verbatim to undirected networks (replace each undirected edge by two opposite directed edges of the same capacity), to networks with vertex capacities (split each capacitated vertex into an in-vertex and out-vertex joined by an edge of that capacity), and to multiple sources/sinks (attach a super-source/super-sink with infinite-capacity edges). It does not by itself guarantee the maximiser is found in finitely many steps by any particular algorithm — that is a separate, algorithmic question.

Corollaries & converses

Integrality theorem (free corollary of the proof, not the statement). If every capacity \(c(e)\) is an integer, the augmenting-path construction of Steps 8–9 (run from \(f\equiv 0\)) only ever adds an integer \(\delta\) to an integer flow, so it produces, inductively, an integer-valued maximum flow — a genuinely useful strengthening the LP-compactness proof alone does not hand you.
Certificate of optimality. Any flow \(f\) and cut \((S,T)\) with \(|f|=c(S,T)\) are simultaneously certified maximum and minimum respectively, by weak duality (Step 5) alone — this is what makes max-flow algorithms self-verifying.
Menger's theorem (edge-disjoint version) follows as a special case: in a unit-capacity network, the maximum number of edge-disjoint \(s\)-\(t\) paths equals the minimum number of edges whose removal disconnects \(s\) from \(t\).
Converse-type statement, and why it is not really a converse: the theorem is an equality (an "if and only if" is not the right shape to ask for) — but one can ask whether every cut achieving the minimum arises as the "reachability cut" \((S,T)\) of Step 10 from some maximum flow. This is false in general: a network can have several minimum cuts, only some of which are reachability cuts of a particular maximum flow; different maximum flows (when the maximiser is non-unique) can induce different minimum cuts.
No converse recovering flows from cuts. Knowing the minimum cut capacity does not by itself hand you a maximum flow; the proof is genuinely two-directional (existence of \(f^{\ast}\), then construction of a matching cut from it), not a formula invertible in one line.

Fails without

Finiteness of the graph. Ford & Fulkerson's classical infinite-ladder network (an infinite sequence of parallel unit-capacity rungs feeding into a single sink) has every finite partial flow strictly below \(1\) yet no flow of value \(1\) is achievable by conserving flow at every vertex, while every finite cut still has capacity \(\ge 1\); the supremum of achievable flow is not attained, so "\(\max_f\)" in the statement is not even well-posed, and the compactness argument (Steps 6–7) has no finite-dimensional space to work in.
Conservation at internal vertices. Take \(G\) with \(s\to v\to t\), capacities \(c(s,v)=c(v,t)=5\), but allow \(v\) to "leak" flow to the outside world, say pass only \(2\) units through while receiving \(5\). Then a flow of apparent value \(5\) at \(s\) delivers only \(2\) at \(t\); the cut-value lemma \(f(S,T)=|f|\) (Steps 1–3) breaks because the telescoping sum no longer collapses to the single boundary term, so the two sides of the theorem measure genuinely different quantities and need not agree — e.g. the cut \(\{s\}\,|\,\{v,t\}\) still has capacity \(5\), but no flow legally delivers value \(5\) to \(t\) under the leak.
Non-negative capacities. Allowing \(c(e)\lt 0\) on some edge breaks weak duality directly: Step 4's move "\(-\sum_{T\to S} f(e) \le 0\)" used \(f\ge0\), but if capacities can be negative one would in fact want to allow \(f(e)\lt 0\) to make sense of "negative capacity", and then \(f(S,T)\) can exceed \(c(S,T)\) for the minimising cut, so \(\max_f|f|\) can strictly exceed \(\min c(S,T)\).

Common errors

Computing a cut's capacity by summing all edges between \(S\) and \(T\) in either direction, instead of only edges directed from \(S\) to \(T\); edges from \(T\) back into \(S\) do not count towards \(c(S,T)\) even though they are "between" the two sides.
Believing the minimum cut is unique, and reporting "the" minimum cut without checking for others — networks routinely have several cuts of equal minimum capacity, and different maximum flows can single out different ones as their residual-reachability cut.
Stopping the augmenting-path search as soon as no path with strictly increasing flow along every edge is found, forgetting that augmenting paths may need to push backward along an edge already carrying flow (the residual back-edge) — omitting back-edges from the residual graph gives a flow that is only locally, not globally, maximum.
Conflating "maximum flow" with "the algorithm has run out of obvious forward paths"; without building the actual residual graph and checking reachability of \(t\), one can wrongly declare a non-maximum flow to be maximum.
Assuming the integrality corollary applies whenever the answer "looks like" it should be an integer, without checking that all capacities are integers — a single irrational or fractional capacity can force every maximum flow to be non-integral on some edge.
Trying to apply the theorem directly to an undirected graph by using a single capacity per edge without splitting it into two anti-parallel directed edges, which double-counts or under-counts capacity when flow could plausibly go either way.

Discussion

The theorem was proved independently by Ford and Fulkerson, and by Elias, Feinstein and Shannon, in the mid-1950s, motivated explicitly by Cold War logistics questions about the capacity of Soviet railway networks — the min-cut side of the theorem is literally "which set of rail links, if destroyed, does the most damage to throughput", and this military origin is why the algorithmic (not just existential) content of the theorem — actually finding an optimal flow and a matching cut — was prized from the outset.

Structurally, the proof given here is a special case of linear programming duality: the flow polytope \(\mathcal{F}\) and objective \(|f|\) define a linear program whose dual, after a change of variables (indicator of which side of a cut each vertex is on, relaxed and rounded), is exactly the minimum cut problem. This is why the argument bifurcates into a routine "weak duality" half (any feasible pair bounds each other, Steps 1–5, true for every LP dual pair) and a much more delicate "strong duality" half (an optimal pair actually meets, Steps 6–13) — the general LP strong duality theorem would also prove this, but the residual-graph argument here is self-contained and constructive, directly producing both an optimal flow and a matching cut via the same object.

The Ford–Fulkerson method obtained from Steps 8–9 run repeatedly is an algorithm, not merely a proof: start from \(f\equiv 0\) and repeatedly augment along any \(s\)-\(t\) path in the residual graph until none exists. With integer capacities this terminates (each augmentation strictly increases the integer value \(|f|\), which is bounded above by \(\sum_{e\ \text{out of}\ s} c(e)\)), but the number of augmentations can be made exponentially large by an adversarial choice of paths; with irrational capacities, badly-chosen augmenting paths can fail to terminate at all and even converge to a value strictly below the true maximum — a fact that surprised early researchers, since the theorem itself guarantees a maximiser exists (Step 7) but says nothing about which sequence of augmentations reaches it. This is exactly why Edmonds–Karp (always augment along a shortest residual path) and later scaling and preflow-push algorithms were developed: they fix the algorithmic complexity question that the existence theorem leaves entirely open.

A common misconception is that max-flow min-cut somehow requires or implies that maximum flows are unique; they generically are not (any two maximum flows differ by a "circulation" — a flow of value \(0\) supported on cycles of the union of their difference — and this space of circulations can be large), while the theorem only pins down the shared value. A second misconception is treating the theorem as symmetric in \(s\) and \(t\): the value \(|f|\) and the cut orientation are defined relative to a fixed direction, and reversing the roles of \(s,t\) in a directed network generally changes both the maximum flow value and the minimum cut, since edge directions are not reversed along with the relabelling.

Worked examples

\text{Network: } s\to a\ (3),\ s\to b\ (2),\ a\to b\ (1),\ a\to t\ (2),\ b\to t\ (3). \text{ Find } \max_f|f|.

Set-up: apply the augmenting-path construction from \(f\equiv 0\). A

\text{Augment along } s\to a\to t:\ \delta=\min(3,2)=2. \quad \text{Augment along } s\to b\to t:\ \delta=\min(2,3)=2.

Each is a directed path in the current residual graph (equal to \(G\) itself, since \(f\equiv0\)); bottleneck is the minimum edge capacity along the path, Step 9 of the proof. After these, \(f(s,a)=2,f(a,t)=2,f(s,b)=2,f(b,t)=2\), current value \(4\). A

\text{Residual capacities now: } s\to a:1,\ a\to b:1,\ b\to t:1,\ \text{(and back-edges)}. \text{ Augment along } s\to a\to b\to t: \delta=\min(1,1,1)=1.

A genuine third augmenting path exists using the previously-unused edge \(a\to b\); after augmenting, \(f(s,a)=3,\,f(a,b)=1,\,f(b,t)=3\), value now \(4+1=5\). B

\text{Check: } s\to a\ (3/3),\ s\to b\ (2/2),\ a\to b\ (1/1),\ a\to t\ (2/2),\ b\to t\ (3/3) \text{ — every edge saturated, so } S=\{s\},\ T=\{a,b,t\},\ c(S,T)=c(s,a)+c(s,b)=5.

No forward residual edge leaves \(s\), so the reachability set of Step 10 is just \(\{s\}\); the cut capacity computed directly from Step 12 confirms \(5\). A

\max_f|f| = 5 = c(\{s\},\{a,b,t\})

Reading. The network's throughput is entirely bottlenecked by the two edges leaving the source; three augmenting paths exhaust it, and no other route exists once these are saturated.

\text{Network (a bandwidth-planning bridge): } s\to a\ (10),\ s\to b\ (10),\ a\to m\ (3),\ b\to m\ (3),\ m\to t\ (20). \text{ Find } \max_f|f| \text{ and a witnessing cut.}

The two source edges and the sink edge are generously capacitated; the interesting bottleneck should be the pair of edges into \(m\). A

\text{Augment } s\to a\to m\to t:\ \delta=\min(10,3,20)=3. \quad \text{Augment } s\to b\to m\to t:\ \delta=\min(10,3,17)=3.

Second bottleneck uses the updated residual capacity \(20-3=17\) on \(m\to t\); both augmentations legal by Step 9. Running value \(6\); \(f(a,m)=3\) and \(f(b,m)=3\) are now saturated. A

\text{No further augmenting path: } s\to a \text{ and } s\to b \text{ have residual capacity } 7 \text{ each, but } a\to m,\, b\to m \text{ are saturated, so } m \text{ is unreachable from } s \text{ in } G_f.

Reachability set (Step 10): \(S=\{s,a,b\}\), \(T=\{m,t\}\); this is exhaustive since every out-edge of \(a\) and \(b\) other than the saturated ones leads nowhere new. B

c(S,T) = c(a,m) + c(b,m) = 3+3 = 6.

Only edges from \(S=\{s,a,b\}\) to \(T=\{m,t\}\) are \(a\to m\) and \(b\to m\) (the edges \(s\to a, s\to b\) stay inside \(S\); \(m\to t\) stays inside \(T\)); apply Step 12. A

\max_f|f| = 6 = c(\{s,a,b\},\{m,t\})

Reading. Despite ample capacity everywhere else, the network can never carry more than \(6\) units because every unit must cross the narrow "bridge" \(\{a\to m,\, b\to m\}\); the theorem certifies that no cleverer routing could ever beat \(6\), without needing to enumerate all possible flows.

Problems

Network: \(s\to t\ (2)\), \(s\to a\ (3)\), \(a\to t\ (5)\). Find \(\max_f|f|\) and a minimum cut.
Solution

Two edge-disjoint routes exist: the direct edge \(s\to t\) (capacity \(2\)) and the path \(s\to a\to t\) (bottleneck \(\min(3,5)=3\)). Pushing both simultaneously is feasible since they share no edge, giving \(f(s,t)=2,\,f(s,a)=3,\,f(a,t)=3\), value \(5\). Both edges out of \(s\) are now saturated, so \(S=\{s\}\), \(T=\{a,t\}\), giving cut capacity \(c(s,t)+c(s,a)=2+3=5\). Since \(5=5\), by weak duality (Step 5) this flow and this cut are simultaneously optimal: \(\max_f|f|=5\).
Network: \(s\to a\ (4)\), \(s\to b\ (4)\), \(a\to c\ (2)\), \(b\to c\ (2)\), \(c\to t\ (3)\). Find \(\max_f|f|\) and identify the bottleneck.
Solution

All flow from \(s\) must pass through \(c\) before reaching \(t\). Consider the cut \(S=\{s,a,b\}\), \(T=\{c,t\}\): the only crossing edges are \(a\to c\ (2)\) and \(b\to c\ (2)\), giving \(c(S,T)=4\); but also consider \(S'=\{s,a,b,c\}\), \(T'=\{t\}\): the only crossing edge is \(c\to t\ (3)\), giving \(c(S',T')=3\), the smaller of the two, so \(\min_{(S,T)}c(S,T)\le3\). Achieving value \(3\): send \(2\) along \(s\to a\to c\to t\), then only \(1\) more unit of \(c\to t\) capacity remains, so send \(1\) along \(s\to b\to c\to t\); check conservation at \(c\): in \(=2+1=3\), out \(=3\), consistent, and this uses only \(f(a,c)=2\le2\), \(f(b,c)=1\le2\), all within capacity. Value achieved \(=3=c(S',T')\), so by weak duality both are optimal: \(\max_f|f|=3\), with minimum cut \(\{c\to t\}\) alone, the single-edge bottleneck.
Prove: if every edge of \(G\) has capacity exactly \(1\), then \(\max_f|f|\) equals the maximum number of pairwise edge-disjoint directed \(s\)-\(t\) paths (this is the edge-disjoint-paths form of Menger's theorem).
Solution

By the integrality corollary, there is a maximum flow \(f^{\ast}\) with every \(f^{\ast}(e)\in\{0,1\}\) (since capacities are all \(1\), integer bottleneck augmentation keeps flow in \(\{0,1\}\) on every edge throughout Ford–Fulkerson). The sub-digraph of edges with \(f^{\ast}(e)=1\) has, by conservation, in-degree equal to out-degree at every vertex except \(s\) (out-degree exceeds in-degree by \(|f^{\ast}|\)) and \(t\) (in-degree exceeds out-degree by \(|f^{\ast}|\)); standard graph-theoretic decomposition (repeatedly extract an \(s\)-\(t\) path while positive net out-degree remains at \(s\), removing its edges, which cannot create a cycle-only remainder that blocks further extraction because any leftover edges form a balanced sub-digraph decomposable into cycles carrying no net \(s\)-\(t\) value) decomposes this edge set into exactly \(|f^{\ast}|\) edge-disjoint \(s\)-\(t\) paths (plus possibly some cycles, which are discarded as they don't touch \(s\) or \(t\)'s net flow). So \(|f^{\ast}|\) edge-disjoint paths exist. Conversely, \(k\) edge-disjoint \(s\)-\(t\) paths give a feasible unit flow along each, summing to a feasible flow of value \(k\) (no edge used twice since capacity \(1\) and paths edge-disjoint), so \(k\le\max_f|f|\). Hence the maximum number of edge-disjoint paths equals \(\max_f|f|\), which by the main theorem equals \(\min_{(S,T)}c(S,T)\) — the minimum number of edges whose removal separates \(s\) from \(t\), recovering Menger's theorem as a corollary.
Suppose there is no directed path at all from \(s\) to \(t\) in \(G\). Show directly (without invoking the full theorem) that \(\max_f|f|=0\) and exhibit a cut of capacity \(0\).
Solution

Let \(S\) be the set of vertices reachable from \(s\) along directed edges of \(G\) itself (not a residual graph — just \(G\)). Since there is no path from \(s\) to \(t\), \(t\notin S\), so \(T=V\setminus S\) is non-empty and \((S,T)\) is a valid cut. Every edge from \(S\) to \(T\) would put its head in \(S\) by definition of reachability, contradiction — so there are no edges from \(S\) to \(T\) at all, giving \(c(S,T)=0\). By weak duality (Step 5 of the proof, which needs only the capacity constraint and non-negativity, not the full theorem), \(|f|\le c(S,T)=0\) for every feasible flow \(f\); since \(f\equiv0\) is feasible with value \(0\), \(\max_f|f|=0\).
Let \(G\) have all-integer capacities and let \(f\) be any maximum flow (not necessarily produced by integer augmentation). Prove \(f\) is nonetheless forced to be integer-valued on every edge whose value is not shared by multiple distinct maxima — more precisely, prove the Integrality Theorem: at least one maximum flow with all-integer values exists.
Solution

Run the Ford–Fulkerson construction of Steps 8–9 starting from \(f_0\equiv0\), which is integer-valued. Inductively, suppose \(f_k\) is integer-valued; if an augmenting path exists in \(G_{f_k}\), its residual capacities \(r(e)=c(e)-f_k(e)\) or \(r(e)=f_k(e)\) are differences/values of integers (capacities integer by hypothesis, \(f_k\) integer by inductive hypothesis), hence integers, so \(\delta=\min_i r(e_i)\) is a positive integer, and \(f_{k+1}=f_k\pm\delta\) on the path edges remains integer-valued. This process must terminate: \(|f_k|\) strictly increases by the positive integer \(\delta\ge1\) at each step while staying bounded above by \(\sum_{e\ \text{out of}\ s}c(e)\) (itself a finite integer, weak duality Step 4), so after finitely many steps no augmenting path remains. By Steps 9–13 the resulting \(f^{\ast}\) is then a maximum flow, and by the inductive construction it is integer-valued on every edge. Hence an integer-valued maximum flow exists (though, as the Discussion notes, it need not be the unique maximum flow — non-integer maxima can coexist with it when the maximiser is non-unique).