5. (20 pts.) Consider the following flow network (Figure 2) with source s, sink t and capacities on the edges. m 'm S m 1 1 r V1 V2 V3 V4 m m t Figure 2: Flow network (√5-1) where r = and m 2 is an integer. 2 m (a) Show that the maximum flow of the network is 2m + 1. (b) Consider the potential s-t paths po = {s, v2, v3,t}, p₁ = {s, V4, V3, V2, V1,t}, P2 = {S, V2, V3, V4,t} and p3={s, V1, V2, V3,t} in the residual graphs of the Ford-Fulkerson algorithm. Suppose that the algorithm chooses to augment along the paths po, P1, P2, P1, P3, P1, P2, P1, P3, P1, P2, P1, P3, ... in this order. Show (using induction) that after augmenting along p3, the residual capacities of edges (v2, v1), (V4, V3) and (v2, v3) are always of the form rk, k+1 and 0 respectively for some k = N. (c) Show that if we use the augmenting paths in the sequence above an infinite number of times, the total flow converges to 3+2r. (Note that since the max flow is 2m+1, this show that the Ford-Fulkerson algorithm never terminates and the flow doesn't even converge to the maximum flow.)