Suppose that each edge e = (u, v) in a flow network g = (v, e) has not only an upper bound ce on the net flow from u to v, but also a lower bound be. that is, any flow f in the network must satisfy be ≤ f(e) ≤ ce, for all edges e. it may be the case that for a network no such feasible flow exists. for a cut (a, b), let us define c(a, b) = p e=(u, v),u∈a, v∈b ce, and b(a, b) = p e=(u, v),u∈a, v∈b be.
(a) prove that if f is a flow in the network, then the value v(f) of the flow satisfies v(f) ≤ c(a, b) − b(b, a) for any cut (a, b) of g.
(b) prove that the value of a maximum flow in the network, if it exists, is the minimum value of c(a, b) − b(b, a) over all cuts (a, b) of the network.