[proofplan] We remove the lower bounds by writing each feasible circulation as $f=l+g$, so the problem becomes finding an integral nonnegative flow $g$ with integer capacities and prescribed integer node imbalances. We then encode those prescribed imbalances as a standard maximum-flow problem by adding a super-source and a super-sink. The assumed real feasible circulation gives a saturating flow in the auxiliary network, and the integral maximum-flow theorem produces an integral saturating flow. Restricting that integral auxiliary flow to the original arcs gives an integral $g$, hence $f_{\mathbb{Z}}=l+g$ is integral and satisfies the original constraints. [/proofplan] [step:Remove the lower bounds and compute the residual balance] For an arc $a\in A$, let $\operatorname{tail}(a)\in V$ denote its initial vertex and let $\operatorname{head}(a)\in V$ denote its terminal vertex. Define the residual capacity function $c:A\to \mathbb{Z}_{\geq 0}$ by \begin{align*} c(a)=u(a)-l(a) \end{align*} for every $a\in A$. Define the lower-bound imbalance function $r:V\to \mathbb{Z}$ by \begin{align*} r(v)=\sum_{a\in A,\,\operatorname{tail}(a)=v} l(a)-\sum_{a\in A,\,\operatorname{head}(a)=v} l(a) \end{align*} for every $v\in V$, and define the residual balance function $d:V\to \mathbb{Z}$ by \begin{align*} d(v)=b(v)-r(v). \end{align*} Let $f:A\to \mathbb{R}$ be a feasible circulation with balance $b$. Define $g:A\to \mathbb{R}$ by \begin{align*} g(a)=f(a)-l(a) \end{align*} for every $a\in A$. Since $l(a)\leq f(a)\leq u(a)$, we have \begin{align*} 0\leq g(a)\leq u(a)-l(a)=c(a) \end{align*} for every $a\in A$. Also, for every $v\in V$, substituting $g=f-l$ into the outgoing-minus-incoming balance gives \begin{align*} \sum_{a\in A,\,\operatorname{tail}(a)=v} g(a)-\sum_{a\in A,\,\operatorname{head}(a)=v} g(a)=\sum_{a\in A,\,\operatorname{tail}(a)=v} (f(a)-l(a))-\sum_{a\in A,\,\operatorname{head}(a)=v} (f(a)-l(a))=b(v)-r(v)=d(v). \end{align*} Thus the assumed feasible circulation is equivalent, after subtracting the integer lower bounds, to a real function $g:A\to\mathbb{R}$ with capacities $0\leq g\leq c$ and node balance $d$. [guided] For an arc $a\in A$, write $\operatorname{tail}(a)\in V$ for the initial vertex of $a$ and $\operatorname{head}(a)\in V$ for the terminal vertex of $a$. The lower bounds are the only obstruction to applying a standard integral-flow theorem directly, because standard maximum-flow problems have lower bound $0$ on every arc. We therefore shift every arc variable by its lower bound. Define the residual capacity function $c:A\to \mathbb{Z}_{\geq 0}$ by \begin{align*} c(a)=u(a)-l(a) \end{align*} for every arc $a\in A$. This is integer-valued and nonnegative because $u(a),l(a)\in\mathbb{Z}$ and $l(a)\leq u(a)$. Define $r:V\to\mathbb{Z}$ by \begin{align*} r(v)=\sum_{a\in A,\,\operatorname{tail}(a)=v} l(a)-\sum_{a\in A,\,\operatorname{head}(a)=v} l(a) \end{align*} for every vertex $v\in V$. This is the net balance already forced by the lower bounds. Define $d:V\to\mathbb{Z}$ by \begin{align*} d(v)=b(v)-r(v). \end{align*} Thus $d(v)$ is the extra balance that remains to be supplied by the residual variables. Now let $f:A\to\mathbb{R}$ be the feasible circulation assumed in the theorem. Define $g:A\to\mathbb{R}$ by \begin{align*} g(a)=f(a)-l(a) \end{align*} for every $a\in A$. The capacity inequalities for $f$ imply \begin{align*} 0\leq f(a)-l(a)\leq u(a)-l(a), \end{align*} so \begin{align*} 0\leq g(a)\leq c(a) \end{align*} for every $a\in A$. We now compute the balance of $g$ at a fixed vertex $v\in V$. Using the definition $g=f-l$ and grouping the terms according to outgoing and incoming arcs gives \begin{align*} \sum_{a\in A,\,\operatorname{tail}(a)=v} g(a)-\sum_{a\in A,\,\operatorname{head}(a)=v} g(a)=\sum_{a\in A,\,\operatorname{tail}(a)=v} (f(a)-l(a))-\sum_{a\in A,\,\operatorname{head}(a)=v} (f(a)-l(a))=b(v)-r(v)=d(v). \end{align*} So the original problem is reduced to finding an integral residual flow $g$ with integer capacities $c$ and prescribed residual balances $d$. [/guided] [/step] [step:Build an auxiliary maximum-flow network whose saturating flows encode the residual balance] Let $V_+=\{v\in V:d(v)>0\}$ and $V_-=\{v\in V:d(v)<0\}$. Because every original arc contributes once with positive sign at its tail and once with negative sign at its head, summing the residual balance equations over all vertices gives \begin{align*} \sum_{v\in V} d(v)=0. \end{align*} Hence \begin{align*} B:=\sum_{v\in V_+} d(v)=\sum_{v\in V_-} (-d(v)). \end{align*} Construct a directed network $N=(V',A')$ as follows. Let $s$ and $t$ be two new vertices not in $V$, and set \begin{align*} V'=V\cup\{s,t\}. \end{align*} The arc set $A'$ consists of the original arcs $A$, together with one arc $s\to v$ for every $v\in V_+$ and one arc $v\to t$ for every $v\in V_-$. Define the capacity function $C:A'\to\mathbb{Z}_{\geq 0}$ as follows: set $C(a)=c(a)$ for every $a\in A$, set $C(s\to v)=d(v)$ for every $v\in V_+$, and set $C(v\to t)=-d(v)$ for every $v\in V_-$. All capacities in $N$ are integers. Define $G:A'\to\mathbb{R}_{\geq 0}$ by setting $G(a)=g(a)$ for $a\in A$, $G(s\to v)=d(v)$ for $v\in V_+$, and $G(v\to t)=-d(v)$ for $v\in V_-$. The capacity inequalities for $g$ and the definitions above show that $0\leq G(\alpha)\leq C(\alpha)$ for every $\alpha\in A'$. For a vertex $v\in V_+$, the conservation equation in $N$ is \begin{align*} d(v)+\sum_{a\in A,\,\operatorname{head}(a)=v} g(a)=\sum_{a\in A,\,\operatorname{tail}(a)=v} g(a), \end{align*} which is equivalent to the residual balance equation at $v$. For $v\in V_-$, the conservation equation is \begin{align*} \sum_{a\in A,\,\operatorname{head}(a)=v} g(a)=\sum_{a\in A,\,\operatorname{tail}(a)=v} g(a)+(-d(v)), \end{align*} again equivalent to the residual balance equation. For $v\in V\setminus(V_+\cup V_-)$, conservation is exactly the residual balance equation with $d(v)=0$. Thus $G$ is an $s$-$t$ flow in $N$ with value $B$, saturating all arcs out of $s$ and all arcs into $t$. [guided] The auxiliary network is designed so that positive residual balance is supplied by the super-source and negative residual balance is drained into the super-sink. Define \begin{align*} V_+=\{v\in V:d(v)>0\},\qquad V_-=\{v\in V:d(v)<0\}. \end{align*} Since each original arc has one tail and one head, the sum over all vertices of outgoing residual flow minus incoming residual flow is zero. Therefore \begin{align*} \sum_{v\in V}d(v)=0, \end{align*} and hence the total positive demand equals the total negative demand: \begin{align*} B:=\sum_{v\in V_+}d(v)=\sum_{v\in V_-}(-d(v)). \end{align*} Construct $N=(V',A')$ by adjoining two new vertices $s$ and $t$, setting $V'=V\cup\{s,t\}$, adding an arc $s\to v$ for each $v\in V_+$, and adding an arc $v\to t$ for each $v\in V_-$. Define $C:A'\to\mathbb{Z}_{\geq0}$ by $C(a)=c(a)$ on original arcs, $C(s\to v)=d(v)$ for $v\in V_+$, and $C(v\to t)=-d(v)$ for $v\in V_-$. These capacities are nonnegative integers by the definitions of $V_+$, $V_-$, $c$, and $d$. Define $G:A'\to\mathbb{R}_{\geq0}$ by $G(a)=g(a)$ on $A$, by $G(s\to v)=d(v)$ for $v\in V_+$, and by $G(v\to t)=-d(v)$ for $v\in V_-$. The bounds $0\leq g(a)\leq c(a)$ give $0\leq G(\alpha)\leq C(\alpha)$ for every arc $\alpha\in A'$. It remains to check conservation at original vertices. If $v\in V_+$, then the added arc $s\to v$ contributes incoming flow $d(v)$, so conservation says \begin{align*} d(v)+\sum_{a\in A,\,\operatorname{head}(a)=v}g(a)=\sum_{a\in A,\,\operatorname{tail}(a)=v}g(a), \end{align*} which is exactly the residual balance equation. If $v\in V_-$, then the added arc $v\to t$ contributes outgoing flow $-d(v)$, so conservation says \begin{align*} \sum_{a\in A,\,\operatorname{head}(a)=v}g(a)=\sum_{a\in A,\,\operatorname{tail}(a)=v}g(a)+(-d(v)), \end{align*} again equivalent to the residual balance equation. If $v\notin V_+\cup V_-$, then $d(v)=0$ and no added arc is incident to $v$, so conservation is precisely the residual balance equation with zero right-hand side. Hence $G$ is an $s$-$t$ flow of value $B$ saturating all arcs out of $s$ and all arcs into $t$. [/guided] [/step] [step:Apply integrality of maximum flow to obtain an integral saturating auxiliary flow] The auxiliary network $N$ is finite because the theorem assumes that $D=(V,A)$ is finite, and all capacities $C(\alpha)$ are integers. Since the real flow $G:A'\to\mathbb{R}_{\geq 0}$ has value $B$, the maximum $s$-$t$ flow value in $N$ is at least $B$. On the other hand, every $s$-$t$ flow has value at most the total capacity leaving $s$, namely \begin{align*} \sum_{v\in V_+} C(s\to v)=\sum_{v\in V_+}d(v)=B. \end{align*} Therefore the maximum flow value in $N$ is exactly $B$. By the [Integral Flow Theorem](/theorems/TEMP-17), because $N$ is a finite network with integer capacities, there exists a maximum $s$-$t$ flow $G_{\mathbb{Z}}:A'\to\mathbb{Z}_{\geq 0}$ of value $B$. Since its value equals the total capacity of the arcs leaving $s$, every arc $s\to v$ with $v\in V_+$ is saturated. Since the total capacity of the arcs entering $t$ is also $B$, every arc $v\to t$ with $v\in V_-$ is saturated. [guided] At this point the auxiliary network has converted the circulation problem into a standard maximum-flow problem. The hypotheses needed for the integral maximum-flow theorem are exactly the following: the network is finite, and every arc capacity is an integer. The network $N=(V',A')$ is finite because the theorem assumes that $D=(V,A)$ is finite and we added only two vertices and finitely many arcs. Every capacity is integer-valued because $c=u-l$ is integer-valued on the original arcs, while the new capacities are $d(v)$ or $-d(v)$ and $d:V\to\mathbb{Z}$. We first identify the maximum flow value. The real auxiliary flow $G:A'\to\mathbb{R}_{\geq 0}$ constructed in the previous step has value \begin{align*} B=\sum_{v\in V_+}d(v). \end{align*} Therefore the maximum flow value is at least $B$. Conversely, any $s$-$t$ flow can send out of $s$ no more than the total capacity of the arcs leaving $s$. That total capacity is \begin{align*} \sum_{v\in V_+} C(s\to v)=\sum_{v\in V_+}d(v)=B. \end{align*} Thus no $s$-$t$ flow can have value greater than $B$, and the maximum flow value is exactly $B$. Now apply the [Integral Flow Theorem](/theorems/TEMP-17). It gives an $s$-$t$ flow \begin{align*} G_{\mathbb{Z}}:A'\to\mathbb{Z}_{\geq 0} \end{align*} whose value is the maximum value $B$. Because the total capacity leaving $s$ is already $B$, a flow of value $B$ must use all that capacity. Hence, for every $v\in V_+$, \begin{align*} G_{\mathbb{Z}}(s\to v)=C(s\to v)=d(v). \end{align*} Similarly, the total capacity entering $t$ is \begin{align*} \sum_{v\in V_-} C(v\to t)=\sum_{v\in V_-}(-d(v))=B, \end{align*} so a flow of value $B$ must also saturate every arc entering $t$. Hence, for every $v\in V_-$, \begin{align*} G_{\mathbb{Z}}(v\to t)=C(v\to t)=-d(v). \end{align*} These saturation identities are what recover the prescribed residual balance at each original vertex. [/guided] [/step] [step:Restrict the integral auxiliary flow to recover an integral feasible circulation] Define $g_{\mathbb{Z}}:A\to\mathbb{Z}_{\geq 0}$ by \begin{align*} g_{\mathbb{Z}}(a)=G_{\mathbb{Z}}(a) \end{align*} for every original arc $a\in A$. Since $G_{\mathbb{Z}}$ respects the auxiliary capacities, for every $a\in A$ we have \begin{align*} 0\leq g_{\mathbb{Z}}(a)\leq c(a). \end{align*} The conservation equations for $G_{\mathbb{Z}}$ at vertices of $V$, together with saturation of the added arcs, give, for every $v\in V$, \begin{align*} \sum_{a\in A,\,\operatorname{tail}(a)=v} g_{\mathbb{Z}}(a)-\sum_{a\in A,\,\operatorname{head}(a)=v} g_{\mathbb{Z}}(a)=d(v). \end{align*} Indeed, if $v\in V_+$, the saturated arc $s\to v$ contributes incoming flow $d(v)$; if $v\in V_-$, the saturated arc $v\to t$ contributes outgoing flow $-d(v)$; and if $d(v)=0$, no added arc is incident to $v$ except through the original graph. [guided] We now discard the artificial arcs and keep only the values of the integral auxiliary flow on the original graph. Define $g_{\mathbb{Z}}:A\to\mathbb{Z}_{\geq0}$ by \begin{align*} g_{\mathbb{Z}}(a)=G_{\mathbb{Z}}(a) \end{align*} for every $a\in A$. Since $G_{\mathbb{Z}}$ obeys the capacities in $N$, its restriction satisfies \begin{align*} 0\leq g_{\mathbb{Z}}(a)\leq c(a) \end{align*} for every $a\in A$. The saturation identities recover the residual balance. If $v\in V_+$, then $G_{\mathbb{Z}}(s\to v)=d(v)$; if $v\in V_-$, then $G_{\mathbb{Z}}(v\to t)=-d(v)$; and if $d(v)=0$, no added source or sink arc is attached to $v$. Therefore conservation of $G_{\mathbb{Z}}$ at the original vertex $v$ gives \begin{align*} \sum_{a\in A,\,\operatorname{tail}(a)=v}g_{\mathbb{Z}}(a)-\sum_{a\in A,\,\operatorname{head}(a)=v}g_{\mathbb{Z}}(a)=d(v). \end{align*} Define $f_{\mathbb{Z}}:A\to\mathbb{Z}$ by \begin{align*} f_{\mathbb{Z}}(a)=l(a)+g_{\mathbb{Z}}(a) \end{align*} for every $a\in A$. This is integer-valued because both summands are integers. The inequalities $0\leq g_{\mathbb{Z}}(a)\leq c(a)=u(a)-l(a)$ imply \begin{align*} l(a)\leq f_{\mathbb{Z}}(a)\leq u(a). \end{align*} Finally, substituting $f_{\mathbb{Z}}=l+g_{\mathbb{Z}}$ into the outgoing-minus-incoming balance at $v\in V$ gives \begin{align*} \sum_{a\in A,\,\operatorname{tail}(a)=v} f_{\mathbb{Z}}(a)-\sum_{a\in A,\,\operatorname{head}(a)=v} f_{\mathbb{Z}}(a)=r(v)+d(v)=b(v). \end{align*} Thus $f_{\mathbb{Z}}$ is an integer feasible circulation with node balance $b$. [/guided] Finally define $f_{\mathbb{Z}}:A\to\mathbb{Z}$ by \begin{align*} f_{\mathbb{Z}}(a)=l(a)+g_{\mathbb{Z}}(a) \end{align*} for every $a\in A$. Since both $l(a)$ and $g_{\mathbb{Z}}(a)$ are integers, $f_{\mathbb{Z}}(a)\in\mathbb{Z}$. The capacity bounds follow from $0\leq g_{\mathbb{Z}}(a)\leq u(a)-l(a)$: \begin{align*} l(a)\leq f_{\mathbb{Z}}(a)\leq u(a). \end{align*} For each $v\in V$, substituting $f_{\mathbb{Z}}=l+g_{\mathbb{Z}}$ into the outgoing-minus-incoming balance gives \begin{align*} \sum_{a\in A,\,\operatorname{tail}(a)=v} f_{\mathbb{Z}}(a)-\sum_{a\in A,\,\operatorname{head}(a)=v} f_{\mathbb{Z}}(a)=\sum_{a\in A,\,\operatorname{tail}(a)=v} (l(a)+g_{\mathbb{Z}}(a))-\sum_{a\in A,\,\operatorname{head}(a)=v} (l(a)+g_{\mathbb{Z}}(a))=r(v)+d(v)=b(v). \end{align*} Thus $f_{\mathbb{Z}}$ is an integer feasible circulation with node balance $b$. [/step]