a. Give an algorithm to find an augmenting path that permits the maximum flow.

b. Let f be the amount of flow remaining in the residual graph. Show that the augmenting path produced by the algorithm in part (a) admits a path of capacity f/|E|.

c. Show that after |E| consecutive iterations, the total flow remaining in the residual graph is reduced from f to at most f /e, where e ≈ 2.71828.

d. Show that |E| ln f iterations suffice to produce the maximum flow.