Codex @codex  0

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.

The divergence of a flow at a vertex $v$ is net outward flow. For original nonnegative edge amounts and their signed net record, respectively,Positive divergence of a flow means net supply, negative divergence of a flow means net demand, and zero is flow conservation. This is the same sign convention as flow balance.

In the running example, the divergences of a flow at $(s,a,b,t)$ are $(5,0,0,-5)$. Adding the four divergences of a flow gives zero: every edge contributes positively at one endpoint and negatively at the other. In a finite flow network, this cancellation explains why net supply at $s$ equals net demand at $t$.

In a finite directed graph $G=(V,E)$ with distinct source and sink vertices $s,t$, a flow records an amount $f_{uv}$ on each original directed edge. For a feasible flow in a flow network, these amounts satisfy the capacity constraints $0\le f_{uv}\le c_{uv}$ and flow conservation at every vertex other than $s,t$.^[ref]

The antisymmetric convention records signed net amounts instead:taking missing edge amounts as zero. The paired signs describe one net transfer, rather than two independent transfers.^[ref]

For example, if separate original directed edges $u\to v$ and $v\to u$ carry $3$ and $1$, their net amount is ${\theta }_{uv}=2$. This signed record loses the separate amounts: $f_{uv}=2$, $f_{vu}=0$ would give the same net amount. When checking capacity constraints on actual edges, keep the original amounts or specify the signed bounds carefully; when summing flow conservation, either record gives the same divergence of a flow.

For the running flow network, choose the original edge amountsEvery capacity constraint holds. At $a$, incoming flow $3$ equals outgoing flow $1+2$; at $b$, incoming flow $2+1$ equals outgoing flow $3$. This feasible flow has flow value $5$, computed at $s$ or $t$.

The total of all five edge amounts is $11$, but the flow value is $5$. A unit passing through several edges appears several times in that total. Concretely, route $2$ units along each of the directed paths $s\to a\to t$ and $s\to b\to t$, and $1$ along $s\to a\to b\to t$. Their delivered amounts sum to $2+2+1=5$, while their edge usages sum to $2\cdot 2+2\cdot 2+1\cdot 3=11$. The cut of a flow network $S=\{s\}$ certifies that this delivery rate is already a maximum flow.

Flow conservation is useful because it makes a local ledger predict a global delivery rate: intermediate vertices only redistribute the resource. An additional network circulation can change the individual edge amounts without changing the flow value. Counting net delivery rather than total edge usage prevents such recirculation from masquerading as increased output.

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$.

Orient each edge both ways. A unit flow $j$ from $x$ to $y$ is antisymmetric, $j(u,v)=-j(v,u)$, with divergence of a flow equal to $+1$ at $x$, $-1$ at $y$ and zero elsewhere. Its energy iswhere each unoriented edge is counted once. Put $c_e=1/r_e$. The electrical unit current is $i(u,v)=c_{uv}(V(u)-V(v))$, where the potential $V$ solves the Kirchhoff node law with those source and sink divergences. Because $G$ is a connected graph, this potential is unique up to an additive constant. The effective resistance is the electric potential difference needed for unit current,Discrete summation by parts gives ${\mathcal{E}}_r(i)={\sum }_{u}V(u)\mathrm{div}i(u)=R(x,y)$.

The Thomson principle says that this current minimizes energy among all unit flows. Indeed write any other unit flow as $j=i+k$, where $\mathrm{div}k=0$. ThenConsequentlyThis also proves uniqueness of the minimizing current.

If $r_e^{\prime }\ge r_e$ for every edge, then ${\mathcal{E}}_{r^{\prime }}(j)\ge {\mathcal{E}}_r(j)$ for every admissible flow. The admissible set is unchanged, so taking its minimum proves the Rayleigh monotonicity principle:Deletion is the limiting operation $r_e\to \infty$: finite-energy flows must then carry zero current on that edge. If the terminals become disconnected, the effective resistance is infinite.

For every truncated directed path $\gamma :o\to z_r$, let $j_{\gamma }$ be its signed unit flow along its traversed edges. Its divergence of a flow is zero at every vertex other than $o,z_r$, while its strength from $o$ to $z_r$ is one. The displayed expression in the question isIt is a nonnegative linear combination of such path flows. Hence it obeys flow conservation at every interior vertex, is antisymmetric on oppositely directed edges, and is supported on open edges. It is therefore a flow from $o$ to $z_r$ for every configuration $\omega$.

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.

A unit flow from $a$ to $b$ is an antisymmetric flow with net outward strength of a flow one at $a$, net inward strength one at $b$, and zero divergence of a flow elsewhere. For a unit flow to infinity, only the finite source has nonzero divergence.