Exercises 26.2-10

For one edge pair (u,v) and (v,u), we can eliminate one of them. Suppose that c(u,v) > c(v,u), we can set c’(u,v) = c(u,v) – c(v,u), c’(v,u) = 0. In this way, the number of edges becomes |E|/2 and by the theorem 26.9, the iterations needed by the algorithm is |V||E|/4.