From Conservation to a Cut Identity
A flow is assigned to directed edges, while an \(s\)-\(t\) cut separates the source \(s\) from the sink \(t\). The flow value is measured at the source, but a cut can pass through many edges, including edges whose direction points back toward \(s\). The flow-cut identity explains how these different measurements agree: for every feasible flow and every \(s\)-\(t\) cut, the flow value equals the net flow crossing the cut. Internal flow does not affect this total because it cancels when conservation is summed over the vertices on one side.
Throughout, a network is a finite directed graph \(G=(V,E)\), with distinct vertices \(s,t\in V\) and a capacity \(c(e)\ge 0\) for each directed edge \(e\). A flow \(f\) assigns a real number \(f(e)\) to each edge. It is feasible if \(0\le f(e)\le c(e)\) for every edge, and if flow is conserved at every vertex other than \(s\) and \(t\): total flow entering such a vertex equals total flow leaving it. The value \(|f|\) of a feasible flow is the net flow leaving \(s\), namely flow out of \(s\) minus flow into \(s\). By conservation, this is also the net flow entering \(t\).
In symbols, if \(F^+(S)\) is the set of edges directed from \(S\) to \(V\setminus S\), and \(F^-(S)\) is the set directed from \(V\setminus S\) to \(S\), then the net flow across the cut is \(\sum_{e\in F^+(S)}f(e)-\sum_{e\in F^-(S)}f(e)\). This is different from the cut’s capacity \(c(S,V\setminus S)\), which is the sum of capacities on the forward edges only. A reverse-crossing edge contributes negatively to net flow, but is not part of that capacity sum.
The Flow-Cut Identity
Proof. For each vertex \(v\), let \(b_f(v)\) be its net outflow: the total flow on edges leaving \(v\) minus the total flow on edges entering \(v\). Sum \(b_f(v)\) over all \(v\in S\). An edge with both endpoints in \(S\) contributes its flow once as outflow and once as inflow, so its total contribution is zero. An edge directed from \(S\) to \(V\setminus S\) contributes \(+f(e)\), because it leaves a vertex in \(S\) and enters no vertex in \(S\). An edge directed from \(V\setminus S\) into \(S\) contributes \(-f(e)\). These are all the possibilities, so the sum is exactly the net flow across the cut boundary. \(\square\)
Proof. Apply the Lemma to \(S\). Since \(s\in S\), \(t\notin S\), and flow is conserved at every vertex other than \(s,t\), the sum \(\sum_{v\in S}b_f(v)\) has only one possibly nonzero term: \(b_f(s)\). By definition \(b_f(s)=|f|\). The Lemma says that this same sum is the net flow across the cut. Equating the two expressions gives the identity. This argument applies even if the network is disconnected or has isolated vertices: such vertices either have zero net outflow or contribute no boundary edge. \(\square\)
The identity is a conservation statement, not a claim that the flow equals the cut’s capacity. It says that if a feasible flow is measured by adding its forward crossing values and subtracting its reverse crossing values, the result is the same as measuring the net flow at the source. The following examples check both sides directly.
Worked Example: Two Cuts in a Small Network
Let \(V=\{s,a,t\}\) and let the directed edges be \(s\to a\), \(a\to t\), and \(s\to t\). Give these edges capacities \(5,4,3\), respectively, and flows \(3,3,2\), respectively. Each flow is between zero and its capacity. At \(a\), the incoming flow is \(3\) and the outgoing flow is \(3\), so conservation holds.
The net outflow at \(s\) is \(3+2=5\), so \(|f|=5\). At \(t\), the incoming flow is \(3+2=5\) and there is no outgoing flow, which checks the same value at the sink.
For the cut \(S=\{s\}\), the forward edges are \(s\to a\) and \(s\to t\), and there are no reverse-crossing edges. Its net flow is \(3+2-0=5\), equal to \(|f|\). For \(S=\{s,a\}\), the forward edges are \(a\to t\) and \(s\to t\), and again there are no reverse-crossing edges. Its net flow is \(3+2-0=5\).
Check: Both cuts give \(5\), as does the source calculation \(3+2=5\). Their capacities need not equal the flow value: for \(S=\{s\}\), the capacity is \(5+3=8\); for \(S=\{s,a\}\), it is \(4+3=7\). These capacity sums use capacities on forward edges, not the flow values.
Worked Example: Subtracting Reverse-Crossing Flow
Let \(V=\{s,a,b,t\}\), with directed edges \(s\to a\), \(a\to b\), \(b\to a\), \(a\to t\), and \(b\to t\). Give the edges, in this order, capacities \(4,4,2,2,3\) and flows \(3,3,1,1,2\). Every flow is nonnegative and at most its capacity.
At \(a\), the incoming flow is \(3+1=4\) and the outgoing flow is \(3+1=4\). At \(b\), the incoming flow is \(3\) and the outgoing flow is \(1+2=3\). Thus flow is conserved at both nonterminal vertices. The net outflow at \(s\) is \(3\), so \(|f|=3\); the net inflow at \(t\) is \(1+2=3\).
Now take \(S=\{s,a\}\). The forward crossing edges are \(a\to b\) and \(a\to t\), carrying \(3\) and \(1\). The reverse-crossing edge is \(b\to a\), carrying \(1\). Therefore the net flow across the cut is \((3+1)-1=3\), agreeing with the flow value.
Check: The source calculation gives \(3\), and the cut calculation gives \(4-1=3\). The edge \(b\to a\) must be subtracted because it carries flow into \(S\), not out of \(S\).
Worked Example: A Cut with Several Crossing Edges
Let \(V=\{s,a,b,c,t,z\}\), where \(z\) is isolated, and let the directed edges be \(s\to a\), \(s\to b\), \(a\to b\), \(b\to a\), \(a\to c\), \(b\to c\), and \(c\to t\). Give these edges, in order, capacities \(3,4,3,2,2,5,6\) and flows \(2,3,2,1,1,4,5\). Each flow is nonnegative and no larger than its corresponding capacity.
At \(a\), the incoming flow is \(2+1=3\), and the outgoing flow is \(2+1=3\). At \(b\), the incoming flow is \(3+2=5\), and the outgoing flow is \(1+4=5\). At \(c\), the incoming flow is \(1+4=5\), and the outgoing flow is \(5\). Thus the flow is feasible. The source net outflow is \(2+3=5\), and the sink net inflow is \(5\), so \(|f|=5\).
Choose \(S=\{s,a\}\). The edges leaving \(S\) are \(s\to b\), \(a\to b\), and \(a\to c\), with total flow \(3+2+1=6\). The edge entering \(S\) from outside is \(b\to a\), with flow \(1\). Hence the net flow across the cut is \(6-1=5\).
Check: The cut value \(5\) matches the source value \(2+3=5\) and the sink value \(5\). The isolated vertex \(z\) is outside \(S\) and has no incident edges, so it contributes zero to both sides of the identity.
A Reliable Calculation and a Common Mistake
For a particular flow and cut, a safe calculation has two separate stages. First, calculate \(|f|\) at the source by adding flow leaving \(s\) and subtracting flow entering \(s\). Second, list every edge crossing the cut, mark its direction relative to \(S\), and add forward flow minus reverse-crossing flow. The two calculations should agree when the flow is feasible. If they do not, check the conservation equations, the choice of cut, and the direction signs.
Common mistake: counting only forward crossing flow. In the second example, adding the forward flows gives \(3+1=4\). Calling this the net flow across the cut is wrong: the edge \(b\to a\) carries \(1\) unit into \(S\). The correction is \(4-1=3\), which matches the source value. In general, the forward sum alone is not the flow-cut identity when reverse-crossing flow is present.
The cancellation proof also explains why the cut can contain many internal edges without complicating the formula: each internal edge’s flow appears once with a plus sign and once with a minus sign in the sum of net outflows. Only edges crossing the boundary remain. This is useful when checking a flow from a cut rather than from the source, especially when the cut contains several vertices. The identity holds for every \(s\)-\(t\) cut, not just one chosen cut, and does not depend on the flow being maximum.
Check Your Understanding
For each question, keep forward and reverse-crossing edges distinct, and state the flow value or net flow calculation used.
- Why does an edge with both endpoints in \(S\) contribute zero when net outflows over \(S\) are summed?
- In the second worked example, what is the net flow across \(S=\{s,a,b\}\)? Verify it by listing the crossing edges.
- Can a feasible flow have positive flow on an edge directed into \(s\)? If so, how does that edge enter the definition of \(|f|\)?
- Explain why an isolated vertex in \(S\) does not change the net flow across the cut.
- For the third worked example, calculate the capacity of the cut \(S=\{s,a\}\) and explain why that number is not the net flow across the cut.