This counterexample (from Chvatal [1983]) illustrates how the version of the FordFulkerson method where augmenting paths need not have as few arcs as possible may not terminate for a problem with irrational arc flow bounds. Consider the max-flow problem shown in Fig. 3.12.
(a) Verify that an infinite sequence of augmenting paths is characterized by the table of Fig. 3.12; each augmentation increases the divergence out of the source s but the sequence of divergences converges to a value, which can be arbitrarily smaller than the maximum flow.
(b) Solve the problem with the Ford-Fulkerson method (where the augmenting paths involve a minimum number of arcs, as given in Section 3.2)