(a) Find the maximum flow from s to t in Graph below. Show each augmenting path you use and the resulting residual graph after every other augmenting path (and after the last one if you use an odd number of augmenting paths). Show the final flow graph as well.

(b) Specify a minimum cut which corresponds to the maximum flow you found in part (a). Verify that the s-t cut ({s, C, F, G, H}, {A, B, D, E, I, t}) satisfies the equation

v(f) = f ^(out) (A) ? f ⁽ⁱⁿ⁾ (A).

(c) Suppose you could increase the capacity of one edge in Graph below. Which such increase would result in the greatest increase in the maximum flow for the graph? Explain how the minimum cut form part (b) helps in finding this edge and show the new flow.

3 9 2 8