I want to find, among all minimum cuts in a flow network G with integral capacities, one that contains the smallest number of edges. How can we modify the capacities of G to create a new flow network G' in which any minimum cut in G' is a minimum cut with the smallest number of edges in G. Source - Cormen
Lets say the graph G has n vertices.
We define the capacity for an arc e' in G' which corresponds to the arc e in G as c(e') = c(e) * n + 1.
Therefore the value of a cut in G' is exactly n times the value of the cut in G + the number of edges in the cut.
Lets say we have now a minimum cut in G' with value n * x + a. That means the value of the cut in G is x. If there would exist a cut in G with a smaller value y < x this cut would have a value of n * y + b <= n * (y+1) <= n * x < n * x + a which is a contradiction to the fact that the cut with value n * x + a was minimum in G'. We just proved that every minimum cut in G' is also a minimum cut in G. But then it follows that a minimum cut in G' is a minimum cut in G and has a minimum number of edges of all minimum cuts in G.