[proofplan] We sum the net outflow equation over all vertices in the cut side $S$. At every vertex of $S \setminus \{s\}$, flow conservation makes the net contribution zero, so the total net outflow from $S$ equals the net outflow from the source, namely $|f|$. On the other hand, when the same total is expanded edge-by-edge, every edge internal to $S$ appears once with a positive sign and once with a negative sign, so only edges crossing the cut remain. [/proofplan] [step:Express the flow value as total net outflow from the cut side] Define the net-outflow map $N_f: V \to \mathbb{R}$ by \begin{align*} N_f(v):=\sum_{vw \in E} f(vw)-\sum_{uv \in E} f(uv) \qquad \text{for } v \in V. \end{align*} This argument uses only the definition of flow value and the conservation part of the [feasible flow](/page/Feasible%20Flow) hypothesis; the non-negativity and capacity inequalities are not needed for this identity. The value of the feasible flow $f$ is, by definition, \begin{align*} |f|:=N_f(s)=\sum_{sw \in E} f(sw)-\sum_{us \in E} f(us). \end{align*} By the flow-conservation condition in the definition of a [feasible flow](/page/Feasible%20Flow), $N_f(v)=0$ for every $v \in V \setminus \{s,t\}$. Since $S$ is a [source-sink cut](/page/Source-Sink%20Cut), we have $s \in S$ and $t \notin S$, hence $S \setminus \{s\} \subset V \setminus \{s,t\}$. Because the network is finite, $V$ is finite and therefore $S \subset V$ is finite. Using the decomposition of the finite set $S$ into $\{s\}$ and $S \setminus \{s\}$, \begin{align*} \sum_{v \in S} N_f(v)=N_f(s)+\sum_{v \in S\setminus\{s\}}N_f(v). \end{align*} Flow conservation gives $N_f(v)=0$ for every $v \in S\setminus\{s\}$, and the definition of the value $|f|$ gives \begin{align*} N_f(s)=|f|. \end{align*} Hence \begin{align*} \sum_{v \in S} N_f(v)=|f|. \end{align*} [guided] The purpose of this step is to connect the cut computation to the value of the flow. Define the net-outflow map $N_f: V \to \mathbb{R}$ by \begin{align*} N_f(v):=\sum_{vw \in E} f(vw)-\sum_{uv \in E} f(uv) \qquad \text{for } v \in V. \end{align*} Although $f$ is assumed to be a feasible flow, this particular identity does not use the non-negativity or capacity bounds. It uses only the definition of the value $|f|$ and the conservation equation at vertices other than $s$ and $t$. The value of the feasible flow $f$ is defined to be the net outflow from the source: \begin{align*} |f|:=N_f(s)=\sum_{sw \in E} f(sw)-\sum_{us \in E} f(us). \end{align*} Flow conservation, as part of the definition of a [feasible flow](/page/Feasible%20Flow), says that $N_f(v)=0$ for every vertex $v \in V \setminus \{s,t\}$. Since $S$ is a [source-sink cut](/page/Source-Sink%20Cut), $s \in S$ and $t \notin S$, so every vertex in $S \setminus \{s\}$ lies in $V \setminus \{s,t\}$. Therefore \begin{align*} N_f(v)=0 \qquad \text{for every } v \in S\setminus\{s\}. \end{align*} Because the network is finite, $V$ is finite, and hence $S \subset V$ is finite. Thus the sum over $S$ may be decomposed into the source term and the remaining vertices: \begin{align*} \sum_{v \in S} N_f(v)=N_f(s)+\sum_{v \in S\setminus\{s\}}N_f(v). \end{align*} The second sum vanishes by flow conservation, while $N_f(s)=|f|$ by definition. Hence \begin{align*} \sum_{v \in S} N_f(v)=|f|. \end{align*} [/guided] [/step] [step:Cancel all internal edges in the summed net outflow] Expanding the sum of net outflows over $S$ gives \begin{align*} \sum_{v \in S}N_f(v)=\sum_{v \in S}\left(\sum_{vw \in E} f(vw)-\sum_{uv \in E} f(uv)\right). \end{align*} An edge $uv \in E$ with $u,v \in S$ appears once in the outgoing sum, at vertex $u$, and once in the incoming sum, at vertex $v$, so its two contributions cancel. An edge $uv \in E$ with $u \in S$ and $v \in V\setminus S$ appears only in the outgoing part and contributes $+f(uv)$; these edges are exactly the elements of $\delta^+(S)=\{uv\in E:u\in S,\ v\in V\setminus S\}$. An edge $uv \in E$ with $u \in V\setminus S$ and $v \in S$ appears only in the incoming part and contributes $-f(uv)$; these edges are exactly the elements of $\delta^-(S)=\{uv\in E:u\in V\setminus S,\ v\in S\}$. Edges with both endpoints in $V\setminus S$ do not appear in either sum. Hence \begin{align*} \sum_{v \in S}N_f(v) =\sum_{uv\in\delta^+(S)}f(uv)-\sum_{uv\in\delta^-(S)}f(uv). \end{align*} [guided] We now compute the same quantity $\sum_{v \in S}N_f(v)$ by sorting the edges according to their endpoints. By definition, \begin{align*} \sum_{v \in S}N_f(v)=\sum_{v \in S}\left(\sum_{vw \in E} f(vw)-\sum_{uv \in E} f(uv)\right). \end{align*} Consider any edge $uv \in E$. If $u \in S$ and $v \in S$, then $uv$ is counted once in the outgoing sum for the vertex $u$ and once in the incoming sum for the vertex $v$. Its total contribution is therefore \begin{align*} f(uv)-f(uv)=0. \end{align*} Thus every edge internal to $S$ cancels. If $u \in S$ and $v \in V\setminus S$, then $uv$ is counted in the outgoing sum from $u$, but it is not counted in any incoming sum for a vertex of $S$, because its head $v$ lies outside $S$. Its contribution is $+f(uv)$, and precisely these edges form $\delta^+(S)$. If $u \in V\setminus S$ and $v \in S$, then $uv$ is not counted in any outgoing sum from a vertex of $S$, but it is counted in the incoming sum for $v$. Since incoming terms are subtracted in $N_f(v)$, its contribution is $-f(uv)$, and precisely these edges form $\delta^-(S)$. If $u \in V\setminus S$ and $v \in V\setminus S$, then neither endpoint contributes to a net outflow term indexed by a vertex of $S$, so the edge contributes $0$. Adding the four cases gives exactly \begin{align*} \sum_{v \in S}N_f(v) =\sum_{uv\in\delta^+(S)}f(uv)-\sum_{uv\in\delta^-(S)}f(uv). \end{align*} [/guided] [/step] [step:Identify the two expressions for the same total] The first step showed that \begin{align*} \sum_{v \in S}N_f(v)=|f|. \end{align*} The second step showed that \begin{align*} \sum_{v \in S}N_f(v) =\sum_{uv\in\delta^+(S)}f(uv)-\sum_{uv\in\delta^-(S)}f(uv). \end{align*} Equating these two expressions for the same finite sum gives \begin{align*} |f|=\sum_{uv\in\delta^+(S)}f(uv)-\sum_{uv\in\delta^-(S)}f(uv), \end{align*} which is the desired identity. [/step]