This is a series of problems, leading to a proof that the Ford-Fulkerson algorithm may not halt if some edge capacities are irrational.

Prove that if all edge capacities are rational, Ford-Fulkerson halts.

Solve the recurrence a_{n+2} = a_n - a_{n+1} Use the initial conditions a_0 =1, a_1 = r where r is the root of the characteristic polynomial that has absolute value less than 1. Let S= sum_{n=0}^{n=infinity} a_n

Consider the directed graph G=(V,E) with V= { s, t, x_1 , x_2 , x_3 , x_4 , y_1 , y_2 , y_3 , y_4 } and edges (s, x_i ) for all i, (y_j , t) for all j, (y_i , y_j), (x_i , y_j ), (y_i , x_j ) for all i \= j, and edges e_i = (x_i , y_i ) for i=1, 2, 3, 4. Edges e_i have capacities a_{i-1} (the a_j are the solutions of the recurrence of part 2). All other arcs have capacity S.

Design a strategy that finds paths in the graph G_{f_k }(and corresponding increasing flows f_k such that f_k = a_k Prove your strategy by induction. This yields a flow which is the sum of the a_i

The strategy above yields an infinite sequanece of augmenting flows. Compute the limit (the sum of the series) and compare it with the maximum flow