[proofplan]
We first prove necessity by summing the prescribed node-balance equations over a subset $X\subseteq V$; arcs internal to $X$ cancel, while arcs entering and leaving $X$ contribute with opposite signs. For sufficiency, we remove lower bounds by writing $f=l+g$, obtaining a residual capacity problem with node demands $\hat b$. We then add a source $s^*$ and sink $t^*$, reduce the problem to sending a flow of value $B$ in this auxiliary network, and verify the max-flow cut condition by rewriting each auxiliary cut exactly as the stated cut inequality. Finally, an integral saturating flow in the auxiliary network gives an integer residual flow $g$, and hence the desired circulation $f$.
[/proofplan]
[step:Sum the balance equations to prove the cut inequalities]
Assume first that there exists an integer-valued function $f:A\to\mathbb Z$ satisfying
\begin{align*}
l(a)\leq f(a)\leq u(a)\quad\text{for every }a\in A
\end{align*}
and
\begin{align*}
\sum_{a\in\delta^-(\{v\})}f(a)-\sum_{a\in\delta^+(\{v\})}f(a)=b(v)
\quad\text{for every }v\in V.
\end{align*}
Summing these equations over all $v\in V$, every arc of $A$ appears once with sign $+1$ and once with sign $-1$, so
\begin{align*}
\sum_{v\in V}b(v)=0.
\end{align*}
Now fix a subset $X\subseteq V$. Summing the node-balance equations over $v\in X$, arcs with both endpoints in $X$ cancel, arcs in $\delta^-(X)$ contribute positively, and arcs in $\delta^+(X)$ contribute negatively. Hence
\begin{align*}
\sum_{v\in X}b(v)
=
\sum_{a\in\delta^-(X)}f(a)-\sum_{a\in\delta^+(X)}f(a).
\end{align*}
Using $f(a)\leq u(a)$ for $a\in\delta^-(X)$ and $f(a)\geq l(a)$ for $a\in\delta^+(X)$ gives
\begin{align*}
\sum_{v\in X}b(v)
\leq
\sum_{a\in\delta^-(X)}u(a)-\sum_{a\in\delta^+(X)}l(a).
\end{align*}
This proves necessity.
[/step]
[step:Remove the lower bounds and define the residual balances]
Assume conversely that
\begin{align*}
\sum_{v\in V}b(v)=0
\end{align*}
and that the stated cut inequality holds for every $X\subseteq V$. We seek $f:A\to\mathbb Z$ in the form $f=l+g$, where $g:A\to\mathbb Z$ is a residual flow. Since $l(a)\leq u(a)$ for every $a\in A$ by hypothesis, define the residual capacity function $c:A\to\mathbb Z_{\geq 0}$ by
\begin{align*}
c(a):=u(a)-l(a).
\end{align*}
Then $l(a)\leq f(a)\leq u(a)$ is equivalent to
\begin{align*}
0\leq g(a)\leq c(a).
\end{align*}
Define the residual balance function $\hat b:V\to\mathbb Z$ by declaring, for each vertex $v\in V$,
\begin{align*}
\hat b(v):=
b(v)
-\sum_{a\in\delta^-(\{v\})}l(a)
+\sum_{a\in\delta^+(\{v\})}l(a).
\end{align*}
Then $f=l+g$ has node balance $b$ at $v$ if and only if
\begin{align*}
\sum_{a\in\delta^-(\{v\})}g(a)-\sum_{a\in\delta^+(\{v\})}g(a)=\hat b(v).
\end{align*}
Also,
\begin{align*}
\sum_{v\in V}\hat b(v)
=
\sum_{v\in V}b(v)
-\sum_{v\in V}\sum_{a\in\delta^-(\{v\})}l(a)
+\sum_{v\in V}\sum_{a\in\delta^+(\{v\})}l(a)
=0,
\end{align*}
because each arc contributes once to the double sum over incoming arcs and once to the double sum over outgoing arcs.
[guided]
The lower bounds are inconvenient because a flow variable $f(a)$ is not allowed to start at $0$. We therefore shift each variable by its lower bound. Define a new function $g:A\to\mathbb Z$ by the intended relation $f=l+g$, meaning $f(a)=l(a)+g(a)$ for every arc $a\in A$. Since $l(a)\leq u(a)$, the residual capacity
\begin{align*}
c(a):=u(a)-l(a)
\end{align*}
is a non-negative integer. The capacity condition on $f$ becomes
\begin{align*}
l(a)\leq l(a)+g(a)\leq u(a),
\end{align*}
which is equivalent, after subtracting $l(a)$ from all three terms, to
\begin{align*}
0\leq g(a)\leq c(a).
\end{align*}
Now we compute what balance condition $g$ must satisfy. At a vertex $v\in V$, the desired balance for $f$ is
\begin{align*}
\sum_{a\in\delta^-(\{v\})}f(a)-\sum_{a\in\delta^+(\{v\})}f(a)=b(v).
\end{align*}
Substituting $f(a)=l(a)+g(a)$ gives
\begin{align*}
\sum_{a\in\delta^-(\{v\})}g(a)-\sum_{a\in\delta^+(\{v\})}g(a)
=
b(v)
-\sum_{a\in\delta^-(\{v\})}l(a)
+\sum_{a\in\delta^+(\{v\})}l(a).
\end{align*}
This motivates defining the map $\hat b:V\to\mathbb Z$ by
\begin{align*}
\hat b(v):=
b(v)
-\sum_{a\in\delta^-(\{v\})}l(a)
+\sum_{a\in\delta^+(\{v\})}l(a).
\end{align*}
Thus the residual problem is to find $g:A\to\mathbb Z$ with $0\leq g(a)\leq c(a)$ and incoming-minus-outgoing balance $\hat b(v)$ at every vertex $v$.
We also need the total residual demand to be zero. Summing over all vertices,
\begin{align*}
\sum_{v\in V}\hat b(v)
=
\sum_{v\in V}b(v)
-\sum_{v\in V}\sum_{a\in\delta^-(\{v\})}l(a)
+\sum_{v\in V}\sum_{a\in\delta^+(\{v\})}l(a).
\end{align*}
The first term is zero by hypothesis. In the two double sums, each arc $a\in A$ appears exactly once as an incoming arc of its head and exactly once as an outgoing arc of its tail. Therefore the lower-bound contributions cancel, and
\begin{align*}
\sum_{v\in V}\hat b(v)=0.
\end{align*}
[/guided]
[/step]
[step:Build the auxiliary max-flow network]
Define
\begin{align*}
V^*:=V\cup\{s^*,t^*\},
\end{align*}
where $s^*$ and $t^*$ are new vertices not in $V$. Define an auxiliary directed network on $V^*$ as follows. It contains every original arc $a\in A$ with capacity $c(a)=u(a)-l(a)$. For every $v\in V$ with $\hat b(v)<0$, add an arc $(s^*,v)$ of capacity $-\hat b(v)$. For every $v\in V$ with $\hat b(v)>0$, add an arc $(v,t^*)$ of capacity $\hat b(v)$.
Define
\begin{align*}
B:=\sum_{\{v\in V:\hat b(v)<0\}}-\hat b(v).
\end{align*}
Since $\sum_{v\in V}\hat b(v)=0$, we also have
\begin{align*}
B=\sum_{\{v\in V:\hat b(v)>0\}}\hat b(v).
\end{align*}
Thus the total capacity of arcs leaving $s^*$ equals $B$, and the total capacity of arcs entering $t^*$ also equals $B$.
[/step]
[step:Rewrite every auxiliary cut as the original cut condition]
Let $Y\subseteq V$, and consider the $s^*$-$t^*$ cut whose source side is
\begin{align*}
S_Y:=\{s^*\}\cup (V\setminus Y)
\end{align*}
and whose sink side is
\begin{align*}
T_Y:=Y\cup\{t^*\}.
\end{align*}
Every $s^*$-$t^*$ cut in the auxiliary network has this form for a unique subset $Y\subseteq V$.
The capacity of this cut is
\begin{align*}
C(Y)
=
\sum_{\substack{v\in Y,\, \hat b(v)<0}}-\hat b(v)
+
\sum_{\substack{v\in V\setminus Y,\, \hat b(v)>0}}\hat b(v)
+
\sum_{a\in\delta^-(Y)}(u(a)-l(a)).
\end{align*}
Since
\begin{align*}
B=\sum_{\substack{v\in Y,\, \hat b(v)>0}}\hat b(v)
+
\sum_{\substack{v\in V\setminus Y,\, \hat b(v)>0}}\hat b(v),
\end{align*}
we have
\begin{align*}
C(Y)-B
=
\sum_{a\in\delta^-(Y)}(u(a)-l(a))
-
\sum_{v\in Y}\hat b(v).
\end{align*}
Therefore $C(Y)\geq B$ is equivalent to
\begin{align*}
\sum_{a\in\delta^-(Y)}(u(a)-l(a))\geq \sum_{v\in Y}\hat b(v).
\end{align*}
We now rewrite the right-hand side. By the definition of $\hat b$,
\begin{align*}
\sum_{v\in Y}\hat b(v)
=
\sum_{v\in Y}b(v)
-\sum_{v\in Y}\sum_{a\in\delta^-(\{v\})}l(a)
+\sum_{v\in Y}\sum_{a\in\delta^+(\{v\})}l(a).
\end{align*}
Lower-bound contributions from arcs with both endpoints in $Y$ cancel between the two double sums. Arcs entering $Y$ contribute with sign $-1$, and arcs leaving $Y$ contribute with sign $+1$. Hence
\begin{align*}
\sum_{v\in Y}\hat b(v)
=
\sum_{v\in Y}b(v)
-\sum_{a\in\delta^-(Y)}l(a)
+\sum_{a\in\delta^+(Y)}l(a).
\end{align*}
Substituting this expression into the residual cut inequality gives
\begin{align*}
\sum_{a\in\delta^-(Y)}(u(a)-l(a))
\geq
\sum_{v\in Y}b(v)
-\sum_{a\in\delta^-(Y)}l(a)
+\sum_{a\in\delta^+(Y)}l(a),
\end{align*}
which is equivalent to
\begin{align*}
\sum_{a\in\delta^-(Y)}u(a)-\sum_{a\in\delta^+(Y)}l(a)
\geq
\sum_{v\in Y}b(v).
\end{align*}
This is exactly the assumed cut inequality with $X=Y$. Thus every $s^*$-$t^*$ cut in the auxiliary network has capacity at least $B$.
[guided]
We must check that the auxiliary network can send all supply out of $s^*$ into $t^*$. By the max-flow min-cut principle, the obstruction is a cut of capacity less than the required value $B$. So we compute an arbitrary cut.
Let $Y\subseteq V$ be the set of original vertices placed on the sink side. Then the source side and sink side are
\begin{align*}
S_Y:=\{s^*\}\cup (V\setminus Y).
\end{align*}
The sink side is
\begin{align*}
T_Y:=Y\cup\{t^*\}.
\end{align*}
The arcs crossing from $S_Y$ to $T_Y$ have three types.
First, an auxiliary arc $(s^*,v)$ crosses exactly when $v\in Y$ and $\hat b(v)<0$, and its capacity is $-\hat b(v)$. These contribute
\begin{align*}
\sum_{\substack{v\in Y,\, \hat b(v)<0}}-\hat b(v).
\end{align*}
Second, an auxiliary arc $(v,t^*)$ crosses exactly when $v\in V\setminus Y$ and $\hat b(v)>0$, and its capacity is $\hat b(v)$. These contribute
\begin{align*}
\sum_{\substack{v\in V\setminus Y,\, \hat b(v)>0}}\hat b(v).
\end{align*}
Third, an original arc crosses from $V\setminus Y$ into $Y$ exactly when it belongs to $\delta^-(Y)$, and its residual capacity is $u(a)-l(a)$. These contribute
\begin{align*}
\sum_{a\in\delta^-(Y)}(u(a)-l(a)).
\end{align*}
Therefore the cut capacity is
\begin{align*}
C(Y)
=
\sum_{\substack{v\in Y,\, \hat b(v)<0}}-\hat b(v)
+
\sum_{\substack{v\in V\setminus Y,\, \hat b(v)>0}}\hat b(v)
+
\sum_{a\in\delta^-(Y)}(u(a)-l(a)).
\end{align*}
Now compare this to the required value
\begin{align*}
B=\sum_{\{v\in V:\hat b(v)>0\}}\hat b(v)
=
\sum_{\substack{v\in Y,\, \hat b(v)>0}}\hat b(v)
+
\sum_{\substack{v\in V\setminus Y,\, \hat b(v)>0}}\hat b(v).
\end{align*}
Subtracting gives
\begin{align*}
C(Y)-B
=
\sum_{a\in\delta^-(Y)}(u(a)-l(a))
+
\sum_{\substack{v\in Y,\, \hat b(v)<0}}-\hat b(v)
-
\sum_{\substack{v\in Y,\, \hat b(v)>0}}\hat b(v).
\end{align*}
The last two terms combine to $-\sum_{v\in Y}\hat b(v)$, so
\begin{align*}
C(Y)-B
=
\sum_{a\in\delta^-(Y)}(u(a)-l(a))
-
\sum_{v\in Y}\hat b(v).
\end{align*}
Thus the cut has capacity at least $B$ precisely when
\begin{align*}
\sum_{a\in\delta^-(Y)}(u(a)-l(a))\geq \sum_{v\in Y}\hat b(v).
\end{align*}
It remains to show that this is the same inequality as the one in the theorem. Using the definition of $\hat b$,
\begin{align*}
\sum_{v\in Y}\hat b(v)
=
\sum_{v\in Y}b(v)
-\sum_{v\in Y}\sum_{a\in\delta^-(\{v\})}l(a)
+\sum_{v\in Y}\sum_{a\in\delta^+(\{v\})}l(a).
\end{align*}
An arc with both endpoints in $Y$ appears once in the incoming lower-bound sum and once in the outgoing lower-bound sum, so it cancels. An arc entering $Y$ from $V\setminus Y$ appears only in the incoming lower-bound sum and therefore contributes $-l(a)$. An arc leaving $Y$ appears only in the outgoing lower-bound sum and therefore contributes $+l(a)$. Hence
\begin{align*}
\sum_{v\in Y}\hat b(v)
=
\sum_{v\in Y}b(v)
-\sum_{a\in\delta^-(Y)}l(a)
+\sum_{a\in\delta^+(Y)}l(a).
\end{align*}
Substituting this into the residual cut inequality gives
\begin{align*}
\sum_{a\in\delta^-(Y)}(u(a)-l(a))
\geq
\sum_{v\in Y}b(v)
-\sum_{a\in\delta^-(Y)}l(a)
+\sum_{a\in\delta^+(Y)}l(a),
\end{align*}
and adding $\sum_{a\in\delta^-(Y)}l(a)$ to both sides yields
\begin{align*}
\sum_{a\in\delta^-(Y)}u(a)-\sum_{a\in\delta^+(Y)}l(a)
\geq
\sum_{v\in Y}b(v).
\end{align*}
This is exactly the assumed cut condition.
[/guided]
[/step]
[step:Use a saturating auxiliary flow to recover the feasible circulation]
By the integral form of the [Max-Flow Min-Cut Theorem](/theorems/2568), since $D$ is finite, the auxiliary network is finite, all auxiliary capacities are non-negative integers, and every $s^*$-$t^*$ cut has capacity at least $B$, there exists an integer-valued $s^*$-$t^*$ flow $h$ of value $B$ in the auxiliary network. The non-negativity of the auxiliary capacities follows from $c(a)=u(a)-l(a)\geq 0$ on original arcs, from $-\hat b(v)>0$ on arcs $(s^*,v)$, and from $\hat b(v)>0$ on arcs $(v,t^*)$. Because the total capacity of arcs leaving $s^*$ is $B$, all arcs $(s^*,v)$ with $\hat b(v)<0$ are saturated. Because the total capacity of arcs entering $t^*$ is also $B$, all arcs $(v,t^*)$ with $\hat b(v)>0$ are saturated.
Define $g:A\to\mathbb Z$ on the original arcs by
\begin{align*}
g(a):=h(a).
\end{align*}
For every original arc $a\in A$, the auxiliary capacity constraint gives
\begin{align*}
0\leq g(a)\leq u(a)-l(a).
\end{align*}
Now fix $v\in V$. If $\hat b(v)<0$, the arc $(s^*,v)$ is saturated with value $-\hat b(v)$ and no arc $(v,t^*)$ was added, so flow conservation for $h$ at $v$ gives
\begin{align*}
\sum_{a\in\delta^-(\{v\})}g(a)-\hat b(v)-\sum_{a\in\delta^+(\{v\})}g(a)=0.
\end{align*}
If $\hat b(v)>0$, no arc $(s^*,v)$ was added and the arc $(v,t^*)$ is saturated with value $\hat b(v)$, so flow conservation gives
\begin{align*}
\sum_{a\in\delta^-(\{v\})}g(a)-\sum_{a\in\delta^+(\{v\})}g(a)-\hat b(v)=0.
\end{align*}
If $\hat b(v)=0$, no auxiliary arc incident to $v$ is added for its residual balance, so flow conservation gives
\begin{align*}
\sum_{a\in\delta^-(\{v\})}g(a)-\sum_{a\in\delta^+(\{v\})}g(a)=0.
\end{align*}
In all three cases,
\begin{align*}
\sum_{a\in\delta^-(\{v\})}g(a)-\sum_{a\in\delta^+(\{v\})}g(a)=\hat b(v).
\end{align*}
Finally define $f:A\to\mathbb Z$ by
\begin{align*}
f(a):=l(a)+g(a).
\end{align*}
Then $0\leq g(a)\leq u(a)-l(a)$ implies
\begin{align*}
l(a)\leq f(a)\leq u(a)
\end{align*}
for every $a\in A$. Also, for every $v\in V$,
\begin{align*}
\sum_{a\in\delta^-(\{v\})}f(a)-\sum_{a\in\delta^+(\{v\})}f(a)
=
\sum_{a\in\delta^-(\{v\})}l(a)-\sum_{a\in\delta^+(\{v\})}l(a)
+\hat b(v)
=b(v),
\end{align*}
by the definition of $\hat b(v)$. Therefore $f$ is the desired feasible circulation with node balance $b$.
[/step]
