Consider the gap method described at the end of Section 7.3.2. Suppose that in the course of the preflow-push algorithm the number m(k) of nodes that have price equal to k is 0. Let S be the set of nodes with price less than k, and let S be the complementary set of nodes with price greater than k.
(a) Show that the cut [S,S] is saturated. Hint: The prices of the end nodes of the arcs of the cut differ by at least 2, so by 1-CS, their flows must be at the upper or lower bounds
(b) Explain why the nodes in S can be purged from the computation by setting their prices to N. Hint: For every minimum cut [S , S ], we must have S ⊂ S.