1. 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 .