Let G = (V, E) be a flow network with source s, sink t, and an integer capacity c (u, v) on each edge (u, v) ¬  E. Let C = max (u, v)  Ec (u, v). a. Argue that a minimum cut of G has capacity at most C |E|.
b. For a given number K, show that an augmenting path of capacity at least K can be found in O(E) time, if such a path exists. The following modification of FORD-FULKERSON-METHOD can be used to compute a maximum flow in G.
MAX-FLOW-BY-SCALING (G, s, t)
1 C ← max (u. v)¬ Ec (u, v)
2 initialize flow f to 0
3 K ← 2⌊lgC⌋
4 while K ≥ 1
5 do while there exists an augmenting path p of capacity at least K
6 do augment flow f along p
7 K ← K/2
8 return f
c. Argue that MAX-FLOW-BY-SCALING returns a maximum flow.
d. Show that the capacity of a minimum cut of the residual graph Gf is at most 2K |E| each time line 4 is executed.
e. Argue that the inner while loop of lines 5-6 is executed O (E) times for each value of K.
f. Conclude that MAX-FLOW-BY-SCALING can be implemented so that it runs in O (E2 lg C) time.