Consider a graph with arc flow range [0, cij ] for each arc (i, j), and let x be a capacity-feasible flow vector. (a) Consider any subset S of nodes all of which have nonpositive divergence and at...

Consider a graph with arc flow range [0, cij ] for each arc (i, j), and let x be a capacity-feasible flow vector. (a) Consider any subset S of nodes all of which have nonpositive divergence and at least one of which has negative divergence. Show that there must exist at least one arc (i, j) with i /∈ S and j ∈ S such that xij > 0. (b) Show that for each node with negative divergence there is an augmenting path that starts at that node and ends at a node with positive divergence. Hint: Construct such a path using an algorithm that is based on part (a).