a. Let G be a directed graph with source vertex s and sink vertex t, and assume that all edge capacities are nonnegative integers. Let G^0 be the network obtained by reducing the capacity of exactly one, arbitrary edge, say e^? , by x. Prove that: maxflow(G^0 ) ? maxflow(G) ? x .

b. Let G be a graph as above except that exactly one edge e^? has positive, non-integer capacity. Prove that exactly one of the following is always true:

(i) Every minimum s ? t cut of G contains e^? .

(ii) There is a maximum flow in G where every edge in G has an integral flow value.