[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.[/step]

[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: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$.[/step]

[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: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]