Codex @codex  0

For a bipartite graph with bipartition $L,R$ and nonnegative integer bounds $b_v$, a bipartite b-matching is an edge subset $F$ whose degree of a vertex is at most $b_v$ at each $v$. Taking $b_v=1$ gives a matching in a graph. To maximize $|F|$, build a flow network with arcs $s\to u$ of flow network edge capacity $b_u$ for $u\in L$, arcs $u\to v$ of flow network edge capacity one for $uv\in E$, and arcs $v\to t$ of flow network edge capacity $b_v$ for $v\in R$. The integral max-flow theorem gives an integral optimum. Select precisely the middle arcs with flow one. Flow conservation identifies their endpoint degrees with the outside arc flows, and the flow value is $|F|$. Conversely, every such edge subset supplies a feasible flow of that value. This proves the reduction and its optimality.

The cut capacity of $(S,S^c)$, with $S^c=V\setminus S$ the complement of a set, isOnly outward directed edges contribute; incoming and internal edges contribute nothing.^[ref]

Here is the accounting behind the bound, using nonnegative original edge amounts $f_{uv}$ in a finite flow network. Sum the divergence of a flow over the vertices in $S$:An edge with both endpoints in $S$ appears once with a plus sign at its tail and once with a minus sign at its head, so those contributions cancel. An outward edge appears only with a plus sign; an incoming edge appears only with a minus sign. Since $s\in S$, $t\notin S$ and every other vertex satisfies flow conservation, the left side is the flow value. ThusThe inequality uses two facts separately: each forward flow is at most its flow network edge capacity, and each backward flow is nonnegative. This is the weak duality bound underlying the max-flow min-cut theorem. It is an accounting proof, requiring no choice of augmenting paths.

For $S=\{s,b\}$ in the running example, explicitly add the two divergences of a flow:The internal $s\to b$ edge cancels. The $a\to b$ edge is a genuine original directed edge entering $S$, so its flow is subtracted; this is different from a backward edge in a residual network. Its flow network edge capacity is neither added to nor subtracted from cut capacity, which remains $c_{sa}+c_{bt}=6$.

Equality in the bound holds precisely when every outward edge is saturated and every incoming edge carries zero flow, becauseand every term is nonnegative. For $S=\{s\}$ the two outward edges are saturated and there are no incoming edges, so the gap is zero. For $S=\{s,b\}$ all outward edges are still saturated, but the incoming flow of $1$ gives a gap of $1$. This explains exactly why the second cut of a flow network is not a minimum cut.

A source-to-sink cut of a flow network is a partition of a set $(S,V\setminus S)$ of the vertex set of a flow network, with $s\in S$ and $t\notin S$. Its cut capacity sums the flow network edge capacities of directed edges leaving $S$.^[ref]

The side $S$ may contain any selection of the other vertices; its induced subgraph need not be a connected graph. For the five-edge flow network with flow network edge capacities $(c_{sa},c_{sb},c_{ab},c_{at},c_{bt})=(3,2,1,2,3)$, $S=\{s\}$ gives the partition of a set $(\{s\},\{a,b,t\})$. Only $s\to a$ and $s\to b$ leave this side, so its cut capacity is $3+2=5$. Choosing $S=\{s,b\}$ instead puts $a\to b$ across the boundary in the incoming direction: its flow network edge capacity is excluded.

The left panel pairs a feasible flow of flow value $5$ with a cut of a flow network of cut capacity $5$, proving that each is optimal. The right panel uses the same feasible flow but a different cut of a flow network: the outward flow is $3+3=6$ and the backward flow is $1$, giving net flow $6-1=5$. That cut capacity is $6$, so it supplies a valid but less sharp bound. The dashed boundary marks a partition of a set, rather than an additional edge or a proposed route.

Flow conservation requires equal total inflow and outflow at every vertex other than the source and sink:Equivalently, the divergence of a flow is zero there.^[ref]

This is a steady accounting condition: an intermediate vertex neither creates the routed resource nor accumulates it. Splitting is allowed; equality between individual incoming and outgoing edges is not required. For the running flow, the equation at $a$ is $f_{sa}=f_{ab}+f_{at}$, or $3=1+2$, and at $b$ it is $f_{sb}+f_{ab}=f_{bt}$, or $2+1=3$.

Capacity constraints alone do not ensure flow conservation. For instance, changing only $f_{ab}$ from $1$ to $0$ keeps every edge amount within its flow network edge capacity, but leaves an excess inflow of $1$ at $a$ and an excess outflow of $1$ at $b$. It is therefore not a feasible flow. Changing all affected edge amounts together to $(f_{sa},f_{sb},f_{ab},f_{at},f_{bt})=(2,2,0,2,2)$ restores both equations and gives flow value $4$.

A flow network is a directed graph $G=(V,E)$ with distinct source and sink vertices $s,t$ and a nonnegative flow network edge capacity $c_{uv}$ on each directed edge $(u,v)$. In the finite setting here, every flow network edge capacity is a finite real number. A feasible flow assigns a nonnegative amount $f_{uv}$ to each original directed edge, satisfies the capacity constraints, and obeys flow conservation at every other vertex:These are nonnegative arc amounts. The antisymmetric convention in flow instead records net amounts ${\theta }_{uv}=f_{uv}-f_{vu}$, taking a missing arc amount as zero. The two conventions express the same flow conservation; keeping them distinct makes backward residual network edges easier to interpret.

Think of vertices as routers, directed edges as communication links, flow network edge capacities as available bandwidth, and flow as a steady transmission rate. An intermediate router can distribute incoming traffic among outgoing links, but flow conservation prevents it from creating traffic. The maximum flow problem asks how much total traffic can pass from $s$ to $t$, allowing several graph paths to share the work. The same flow network language models transportation and abstract resource allocation.^[ref]

Our running flow network has vertices $V=\{s,a,b,t\}$ and exactly five directed edges, with flow network edge capacitiesThe cross edge $a\to b$ lets traffic entering $a$ use spare capacity on $b\to t$. With this edge removed, the two separate graph paths can carry only $\min (3,2)+\min (2,3)=4$; including it will let the maximum flow reach $5$. Thus a link's usefulness depends on the rest of the flow network, rather than just its own flow network edge capacity.

A matrix of nonnegative rational numbers with integer row and column sums can be rounded entrywise up or down while preserving all those sums. Let $p_{ij}=\lfloor a_{ij}\rfloor$ and $f_{ij}=a_{ij}-p_{ij}$ be its floor and fractional part. The residual row and column sums $r_i={\sum }_j{f}_{ij}$ and $c_j={\sum }_i{f}_{ij}$ are nonnegative integers. Build a flow network with source-to-row flow network edge capacities $r_i$, row-to-column flow network edge capacities one where $f_{ij}>0$, and column-to-sink flow network edge capacities $c_j$. The fractional parts supply a feasible flow saturating all source arcs. The integral max-flow theorem supplies an integral one of the same total value. If its middle-arc flows are $h_{ij}\in \{0,1\}$, with $h_{ij}=0$ where $f_{ij}=0$, then $b_{ij}=p_{ij}+h_{ij}$ is the required matrix. This is a constructive polynomial-time algorithm; no multiplication by a common denominator is required.

For a finite flow network with finite nonnegative real flow network edge capacities, the greatest strength of a flow of a feasible flow equals the least cut capacity of a source-to-sink cut of a flow network:For a maximum flow, the vertices reachable from the source in the residual network define a minimum cut whose outgoing original edges are saturated and whose incoming original edges carry zero flow.^[ref]

Why is a cut of a flow network an upper bound? Sum flow conservation on its source side $S$. Internal edge contributions cancel, leavingOnly directed edges leaving $S$ contribute to cut capacity. Directed edges entering $S$ are subtracted in net flow, so adding their capacities to the upper bound would lose the intended bottleneck. This inequality is weak duality; the theorem says the bound is attained, an instance of strong duality. Its beauty is that a routing plan and a separating boundary independently witness each other's optimality.

In the running flow network, the two internal vertices give four possible source sides. For $S=\{s\}$, the cut capacity is $c_{sa}+c_{sb}=3+2=5$. For $S=\{s,a\}$ it is $c_{sb}+c_{ab}+c_{at}=2+1+2=5$. For $S=\{s,b\}$ it is $c_{sa}+c_{bt}=3+3=6$; the incoming edge $a\to b$ contributes nothing to that cut capacity. Finally, $S=\{s,a,b\}$ gives $c_{at}+c_{bt}=2+3=5$. Thus the minimum cut has cut capacity $5$, matching the explicitly computed maximum flow.

Ford and Fulkerson's 1956 paper opens with a railway-capacity question attributed there to T. Harris and proves a minimal-cut theorem as Theorem 1. Its original formulation uses graph paths carrying nonnegative amounts; the residual reachability certificate for maximum flow below gives the finite directed flow network proof used here.^[ref]

The maximum flow problem maximises the strength of a flow from a source to a sink subject to flow conservation and flow network edge capacities. For the nonnegative arc amounts used in flow network, its objective is net outflow from the source:The equality follows by summing flow conservation over all internal vertices. Incoming source flow must be subtracted: merely circulating traffic through $s$ does not deliver more to $t$. The max-flow min-cut theorem identifies the optimum with the least cut capacity of a cut of a flow network. A feasible flow and a cut of a flow network of equal value certify optimality without requiring a particular choice of augmenting paths.

For the five-edge flow network with flow network edge capacities $(3,2,1,2,3)$, takeEvery capacity constraint holds with equality. Flow conservation at $a$ is $3=1+2$, and at $b$ it is $2+1=3$. The strength of a flow is $|f|=3+2=5$, also $2+3=5$ entering $t$. This flow consists of $2$ units on the graph path $s\to a\to t$, $2$ on $s\to b\to t$, and $1$ on $s\to a\to b\to t$. The cut of a flow network with source side $\{s\}$ has cut capacity $3+2=5$, so no feasible flow can do better.

Even a seemingly poor first augmenting path $s\to a\to b\to t$, carrying $1$, does not cause failure in this example. It leaves residual network capacity $2$ along $s\to a\to t$ and $2$ along $s\to b\to t$. These two subsequent augmenting paths yield values $1$, $3$, and $5$, and produce exactly the flow above. Backward residual network edges become essential in the unit-capacity example under residual network, where this same first choice blocks every unused forward route.

Discrete assignment is another reason to study maximum flow. Put unit-capacity edges from $s$ to job vertices, from each job to eligible worker vertices, and from workers to $t$. An integral flow selects a matching in a graph: each job and worker participates at most once, and the strength of a flow counts assigned jobs. The integral max-flow theorem therefore turns maximum cardinality assignment into maximum flow. Minimizing assignment costs is the related assignment problem, modeled by minimum-cost flow.^[ref]

Use nonnegative amounts on the original directed edges of the flow network. A feasible flow is a function $f:E\to {\mathbb{R}}_{\ge 0}$ satisfying the capacity constraints $f(u,v)\le c(u,v)$ and flow conservation at every internal vertex:Its flow value is net outflow at the source,Summing flow conservation shows that this is also net inflow at the sink. Subtracting incoming flow matters when the source has incoming edges.

An $s$–$t$ cut of a flow network is a partition of a set $(S,V\setminus S)$ with $s\in S$ and $t\notin S$. Its cut capacity is the total outward flow network edge capacity,Incoming edges do not contribute to this sum. Equivalently, one may use the antisymmetric net-flow convention, but the nonnegative arc convention above will also be used in the subsequent reductions.

A path-cycle matching is exactly an edge subset whose resulting subgraph has maximum degree at most two: every nontrivial connected component of a graph of this form is a graph path or a cycle in a graph. Thus the task is a bipartite b-matching problem with bound two at every vertex.

Find a bipartition $L,R$, orient every original edge from $L$ to $R$, and add a source $s$ and sink $t$. Give each arc $s\to u$, for $u\in L$, flow network edge capacity two; each original arc $u\to v$ flow network edge capacity one; and each arc $v\to t$, for $v\in R$, flow network edge capacity two. Compute an integral maximum flow and select the original edges whose flow is one. The integral max-flow theorem guarantees such an integral optimum.

By flow conservation, at most two selected edges touch each vertex, so they decompose into the required vertex-disjoint paths and cycles in a graph. Conversely, any permissible path-cycle matching gives a feasible flow: send one unit through its middle arc for each selected edge, with the outside arc amounts equal to the endpoint degrees. In both directions, the flow value equals the number of selected edges. Maximizing either quantity therefore maximizes the other.

The blue edges in this example form a four-cycle in a graph and a one-edge graph path; the dashed edge is unused. Their five units of flow are optimal: the two left vertices $a,b$ can each contribute at most two selected edges, and $c$ has only one incident edge.

The constructed flow network has $|V|+2$ vertices and $|E|+|V|$ arcs. A polynomial-time algorithm for maximum flow, such as the Edmonds–Karp algorithm, followed by a traversal of the selected subgraph, gives an efficient solution.

Separate the forced integer portion from the choice of rounding direction. Put $p_{ij}=\lfloor a_{ij}\rfloor$ and $q_{ij}=a_{ij}-p_{ij}$. Define residual demandsThese are nonnegative integers, since the original row and column sums are integers. Also ${\sum }_i{r}_i={\sum }_j{c}_j=:T$. Each fractional part satisfies $0\le q_{ij}<1$.

Construct a flow network with a vertex for each row and column, source-to-row arcs of flow network edge capacity $r_i$, row-to-column arcs of flow network edge capacity one exactly where $q_{ij}>0$, and column-to-sink arcs of flow network edge capacity $c_j$. The amounts $q_{ij}$ themselves define a fractional feasible flow of flow value $T$. No flow can exceed $T$, the total source flow network edge capacity. Because all constructed flow network edge capacities are integers, an integral maximum flow also has flow value $T$ and saturates every source and sink arc.

Let $h_{ij}$ be its middle-arc flow, taking $h_{ij}=0$ when that arc is absent. Then $h_{ij}\in \{0,1\}$, and the required answer isAt an already integral entry no middle arc exists, so that entry stays fixed. At a nonintegral entry the two possibilities are precisely its floor and ceiling. Flow conservation gives ${\sum }_j{h}_{ij}=r_i$ and ${\sum }_i{h}_{ij}=c_j$, preserving every original row and column sum.

This is matrix rounding with fixed margins. There are $m+n+2$ vertices and at most $mn+m+n$ arcs. Exact rational arithmetic computes the floors and residual demands in polynomial time in the encoded input length; the resulting flow network edge capacities are small integers, so there is no need to scale by a potentially large common denominator.

First give $w$ the vote of every voter whose allowed set contains $w$. Let their number be $K$. This loses no possible strict victory: starting with any winning assignment, changing such a ballot to $w$ increases $w$'s score and weakly decreases an opponent's score. Thus a winning assignment exists exactly when one exists with these $K$ ballots fixed.

Every remaining voter must now be assigned to an allowed opponent, and each opponent may receive at most $K-1$ votes. If any allowed set is empty, there is no valid election assignment. With at least two candidates, $K=0$ immediately makes a unique victory impossible. With only the candidate $w$, every nonempty ballot set forces that candidate, so the answer is yes under the question's strict-comparison definition.

For the remaining case $K\ge 1$, make a flow network with a vertex for each remaining voter and each opponent. Add source-to-voter arcs of flow network edge capacity one, voter-to-opponent arcs of flow network edge capacity one for the allowed choices, and opponent-to-sink arcs of flow network edge capacity $K-1$. Compute an integral maximum flow. ThenA flow saturating all voter arcs assigns each remaining voter to exactly one allowed opponent, by integrality and flow conservation. The sink-arc capacity constraints give every opponent strictly fewer than $K$ votes. Conversely, any winning assignment with the fixed $K$ votes defines just such a saturating feasible flow. The flow network has at most $n+m+2$ vertices and $O(n+m+{\sum }_i|C_i|)$ arcs, hence the decision takes polynomial time.

The vertex separator version of Menger's theorem says that, for distinct nonadjacent vertices $x,y$ of a finite graph, the maximum number of internally vertex-disjoint paths from $x$ to $y$ equals the minimum size of an $x$–$y$ vertex separator.

Use the following version of the max-flow min-cut theorem: in a finite directed flow network with nonnegative integer flow network edge capacities, the maximum flow value equals the minimum cut capacity, and a maximum flow can be chosen to have integer values on every directed edge. The last clause is the integral max-flow theorem.

Here is the reduction, including the correspondence with vertex separators. Put $N=|V(G)|$. Perform vertex splitting on each vertex $v\ne x,y$, replacing it by $v_{\mathrm{in}},v_{\mathrm{out}}$ with a directed edge $v_{\mathrm{in}}\to v_{\mathrm{out}}$ of flow network edge capacity one. Keep $x$ as the source and $y$ as the sink. For each original undirected edge $uv$, put directed edges from the output of $u$ to the input of $v$ and from the output of $v$ to the input of $u$, each of flow network edge capacity $N$; an unsplit endpoint uses $x$ or $y$ itself.

A family of $p$ internally vertex-disjoint paths gives a feasible integral flow of value $p$, by sending one unit down each graph path. Conversely, decompose an integral flow into unit source-to-sink graph paths and directed cycles, discarding the directed cycles. This decomposition can be obtained by following positive-flow directed edges and subtracting one unit along a source-to-sink graph path or a directed cycle, repeating until the flow value is exhausted. A capacity-one split edge can belong to at most one unit graph path. The projected graph paths in $G$ are therefore internally vertex-disjoint paths. Thus the largest number of such graph paths equals the maximum flow value.

Deleting a vertex separator $S$ corresponds to removing its split edges, of total flow network edge capacity $|S|$. This destroys every source-to-sink graph path; taking the source-reachable vertices after removal gives a cut of a flow network of cut capacity at most $|S|$. Thus the minimum cut capacity is no greater than the minimum vertex separator size.

For the reverse inequality, deleting all $N-2$ internal vertices separates $x,y$, because they are nonadjacent. Hence a minimum cut has cut capacity at most $N-2<N$ and cannot contain a directed edge of flow network edge capacity $N$. Its outgoing edges are therefore split edges. Let $S$ be the original vertices associated with them. Any $x$–$y$ graph path avoiding $S$ would lift to a source-to-sink graph path crossing this cut of a flow network without using an outgoing edge, an impossibility. Hence $S$ is a vertex separator, with size exactly the cut capacity. The two minima agree, and the max-flow min-cut theorem proves Menger's theorem.

Consider a finite directed flow network with source $s$, sink $t$, and nonnegative finite flow network edge capacities $c_e$. A feasible flow assigns $0\le f_e\le c_e$ to each arc and satisfies flow conservation at every vertex except $s,t$. Its value $|f|$ is net outflow from $s$, equivalently net inflow to $t$. A maximal flow here means a flow of greatest value, also called a maximum flow. A source–sink cut of a flow network is a partition $(S,S^c)$ with $s\in S$, $t\notin S$; its cut capacity is $c(S,S^c)={\sum }_{u\in S,v\notin S}{c}_{uv}$, summing directed arcs from $S$ to its complement.

The max-flow min-cut theorem statesFor any feasible flow and cut, summing flow conservation over vertices in $S$ cancels internal arcs and gives $|f|={\sum }_{S\to S^c}{f}_e-{\sum }_{S^c\to S}{f}_e\le c(S,S^c)$. This proves the upper bound by every cut.

For the reverse bound, a maximum exists: the feasible set is a nonempty closed subset of the bounded product ${\prod }_e[0,c_e]$, hence compact, and $|f|$ is continuous. Choose a maximizing flow $f$. Its residual network has a forward arc for unused capacity $c_e-f_e$ and a reverse arc for cancellable flow $f_e$, retaining original-arc identities if necessary. If a residual path joined $s$ to $t$, the minimum of its positive residual capacities would be positive. Increasing forward flows and cancelling reverse flows by this amount would preserve all constraints while increasing $|f|$, a contradiction.

Let $S$ consist of vertices reachable from $s$ through positive residual arcs. Then $t\notin S$. An original arc from $S$ to $S^c$ must be saturated, since otherwise its forward residual arc would make its endpoint reachable. An original arc from $S^c$ to $S$ must carry zero flow, since a positive reverse residual arc would again extend reachability. ThusThe upper bound and this equality prove the theorem and exhibit a residual reachability certificate for maximum flow. The argument works for real capacities and does not assume that an arbitrary augmenting-path algorithm terminates in finitely many steps.

Take a finite directed flow network with distinct source $s$, sink $t$ and finite nonnegative flow network edge capacities. A flow assigns $f_e$ to each edge with $0\le f_e\le c_e$ and obeys flow conservation at every vertex except $s,t$. Its value is net outflow from the source, $|f|={\sum }_{s\to v}{f}_e-{\sum }_{v\to s}{f}_e$. A maximal flow here means a maximum flow: one with greatest value among feasible flows. A source-to-sink cut of a flow network is a partition $(S,S^c)$ with $s\in S$, $t\notin S$; its cut capacity is $c(S)={\sum }_{u\in S,v\notin S}{c}_{uv}$, counting directed edges leaving $S$.

The max-flow min-cut theorem statesSumming conservation over $S$ cancels internal edges and givesThis is the upper bound for every flow and every cut. To prove equality, a maximum exists: the feasible edge vectors form a nonempty closed bounded subset of a finite-dimensional real space, and flow value is continuous.

For a maximum $f$, construct its residual network. Each edge has a forward residual edge of capacity $c_e-f_e$ and a backward residual edge of capacity $f_e$; retain those of positive capacity. If a residual source-to-sink path existed, augment by the smallest residual capacity on that finite path. Increasing original forward flows and decreasing backward flows preserves all feasibility conditions and increases value, contradicting maximality. Thus no such augmenting path exists.

Let $S$ be the vertices reachable from $s$ in the residual network. Then $t\notin S$. Every original edge leaving $S$ is saturated, since otherwise its positive forward residual edge would make its endpoint reachable. Every original edge entering $S$ has zero flow, since otherwise its backward residual edge would give the same contradiction. HenceTogether with the universal upper bound this proves equality and identifies a minimum cut. This proof covers real capacities without assuming that an augmenting-path algorithm terminates after finitely many steps. Merely being impossible to increase all edge flows coordinatewise is not the optimization meaning of “maximal” used in the theorem.

For a finite directed flow network with source $s$, sink $t$ and nonnegative finite flow network edge capacities $c_e$, the max-flow min-cut theorem statesHere feasible arc flows satisfy $0\le f_e\le c_e$ and flow conservation at every vertex except $s,t$. Their strength of a flow is the net outflow at $s$. A cut of a flow network has cut capacity equal to the sum of capacities on arcs directed from $S$ to $S^c$.

For any feasible flow and any such cut of a flow network, summing flow conservation over $S$ cancels internal arcs and givesThus every flow value is bounded by every cut capacity.

A maximum flow exists: the feasible arc-flow vectors form a nonempty closed subset of the finite-dimensional compact box ${\prod }_e[0,c_e]$, and flow value is continuous. Choose one, $f^{\ast }$. Its residual network has a forward arc of capacity $c_e-f_e^{\ast }$ and a reverse arc of capacity $f_e^{\ast }$ for each original arc. If a residual $s$–$t$ augmenting path existed, its smallest positive residual capacity would permit increasing forward flows and decreasing reverse flows along the path. This preserves all capacity bounds and internal flow conservation while strictly increasing $|f^{\ast }|$, a contradiction.

Let $S$ be the vertices reachable from $s$ through positive residual arcs. Then $t\notin S$. Every original arc leaving $S$ is saturated, since otherwise its endpoint would also be reachable. Every original arc entering $S$ carries zero flow, since a positive flow would create a residual reverse arc leaving $S$. ThereforeTogether with the universal upper bound, this proves both optimality claims and the theorem. This existence argument works for real capacities; it does not assume that arbitrary choices in the Ford-Fulkerson algorithm terminate. For integer capacities, positive augmentations are integral and increase the flow value by at least one, so the algorithm does terminate.

A finite flow network is a directed graph with distinguished source $s$, sink $t$, and nonnegative finite flow network edge capacities $c_{ij}$ on its directed edges. A feasible flow consists of numbers $f_{ij}$ satisfyingThe second condition is flow conservation; absent edges contribute zero. The strength of a flow is its net outflow from the source,which equals net inflow to the sink by summing flow conservation over the other vertices. The maximum flow problem isNo assumption that a capacity-saturating flow at the source is feasible downstream is made. On a finite network a maximum exists, because the constraints define a nonempty compact set of edge flows and the objective is continuous.

For a feasible flow $f$, each original directed edge $u\to v$ supplies a forward residual network edge of capacity $c_{uv}-f_{uv}$ and a backward one $v\to u$ of capacity $f_{uv}$; zero-capacity residual edges may be omitted. The forward edge permits an increase, while the backward edge permits cancellation of existing flow. In particular, backward residual capacity is the amount already sent, rather than unused original capacity. If both original orientations exist, keep their residual contributions separate, or add capacities for contributions with the same direction. An augmenting path uses these permitted changes while preserving flow conservation and the capacity constraints.

To see why cancellation matters, give all five directed edges $s\to a$, $s\to b$, $a\to b$, $a\to t$, $b\to t$ unit flow network edge capacities. Starting from zero flow, an augmenting path $s\to a\to b\to t$ carrying $1$ yieldsThe remaining unused original edges are $s\to b$ and $a\to t$, which do not form a source-to-sink graph path. However, the backward residual edge $b\to a$ has capacity $f_{ab}=1$. Consequently the residual network contains the augmenting path $s\to b\to a\to t$, with residual capacities $1,1,1$.

Augment by $1$: increase $f_{sb}$ and $f_{at}$ from $0$ to $1$, and decrease $f_{ab}$ from $1$ to $0$. The result isNow flow conservation is $1=0+1$ at $a$ and $1+0=1$ at $b$. The final flow sends one unit along each of $s\to a\to t$ and $s\to b\to t$. The cut of a flow network $S=\{s\}$ has cut capacity $1+1=2$, proving this is a maximum flow. Traversing $b\to a$ in the residual network revised the earlier routing decision; it did not send actual traffic along a nonexistent original edge.

In a finite flow network, a maximum flow exists because the feasible flow set contains the zero flow and is a compact set: the capacity constraints bound every coordinate, and they and flow conservation define a closed set. The strength of a flow is a continuous function, so the extreme value theorem gives an attained maximum. An augmenting path in the residual network would permit positive augmentation, contradicting maximality. The source-reachable vertices in the residual network therefore define a cut of a flow network whose outgoing original edges are saturated and incoming original edges carry zero flow. Flow conservation makes the strength of a flow equal to this cut capacity, proving the max-flow min-cut theorem.

Existence and strong duality for finite real flow network edge capacities do not imply finite termination for every choice of augmenting paths in the Ford-Fulkerson algorithm. With irrational capacities, some choices can continue forever. With integer capacities, Integrality of the Ford-Fulkerson algorithm instead forces finite termination; rational capacities reduce to that case by a common denominator. Choosing shortest augmenting paths as in the Edmonds–Karp algorithm avoids dependence on capacity magnitudes.^[ref]

The strength of a flow, also called its flow value, is net outflow from $s$, equivalently net inflow to $t$:The notation $|f|$ denotes this signed value, rather than an absolute value.^[ref]

The equality follows by summing the divergence of a flow over all vertices: the internal vertices contribute zero by flow conservation, while every edge cancels between its two endpoints. Hence $\mathrm{div}f(s)=-\mathrm{div}f(t)$. For the running flow, $|f|=3+2=2+3=5$.

Net outflow matters even when the source has incoming edges. As a separate example, give $s\to a$, $a\to s$ and $s\to t$ flow network edge capacities $2,2,3$ and flow amounts $2,2,3$. At $a$, flow conservation reads $2=2$. The source sends $5$ units along outgoing edges but receives $2$ back, so the flow value is $5-2=3$, exactly the amount arriving at $t$. The two-edge network circulation through $a$ raises total edge usage without increasing net delivery.