Characterization of circular flow We are given a directed graph $G$, capacity $u$, source $s$ and sink $t$. We call a flow from $s$ to $t$ a circular flow if the size of the flow is $0$. We say that function $l: E(G) \to R^{+}_{0}$ is a lower bound for a flow $f$ if for each $e \in E(G)$ we have $l(e) \leq f(e)$. For a subset $U \subseteq V(G)$ we define $\delta^+(U)$ as the set of ingoing edges from $U$ and $\delta^-(U)$ as the set of outgoing edges from $U$
We are to prove that network (G, u, s, t) has a circular flow $f$ with a lower bound $l$ if and only if $l \leq u$ and for every set $U \subseteq V(G)$ the following is true:
$$\sum_{e \in \delta^+(U)}l(e) \leq \sum_{e \in \delta^-(U)}u(e).$$
I have proven the implication from left to right with contradiction - if the inequality is not true, we have a set $U$ for which more flow enters than leaves. If $s \in U$ or $t \in U$ this is in contradiction with the fact that $f$ is circular. Otherwise this is in contradiction with Kirchoff conditions for some of the vertices in $U$.
I couldn't, however, get any idea how to construct a flow with lower bound $l$ if the inequality holds. Any help would be much appreciated.
 A: There is a nice direct proof of this that uses the concept of submodularity (implicitly), see for example here.
I'll outline another solution by reduction to a flow problem. The trick is to look at $f' = f - l$ instead of $f$. This $f'$ kind of looks like a normal flow: we have $0 \leq f'(e) \leq c'(e) = c(e) - l(e)$ for each edge. But unlike a flow, $f'$ is not conserved at the vertices. Instead, using the requirement that $f$ be a circular flow, we have, for each $v \in V$,
$$\sum_{e \in \delta^+(v)} f'(e) - \sum_{e \in \delta^-(v) }f'(e) = \sum_{e \in \delta^-(v)} l(e) - \sum_{e \in \delta^+(v)}l(e).$$ Let's denote the right side above by $L(v)$. Now there are two kinds of vertices: the vertices $v$ with $L(v) \geq 0$ have larger outflow than inflow (according to $f'$); let's call these the positive vertices. Vice versa, the vertices $v$ with $L(v) < 0$ have larger inflow than outflow; let's call them the negative vertices.
Without giving the details, you can decide the existence of such an $f'$ by solving a flow problem in a cleverly constructed new network. In particular, you should add a new source $s^*$ and a new sink $t^*$, and add directed edges with capacities in such a way that each positive vertex $v$ can "get $L(v)$ extra flow from $s^*$" and each negative vertex $v$ can "send $L(v)$ extra flow to $t^*$." More precisely, you can construct a network such that $f'$ exists if and only if in your new network there is a flow of size $$ \sum_{v \text{ is positive}}L(v).$$ If you take the MFMC criterion in this network back to your original network, you will get back the original criterion.
