Cormen's Algorithms 3rd edition Exercise 26.2-13 Page 731:
Suppose that you wish to find, among all minimum cuts in a flow network G with integral capacities, one that contains the smallest number of edges. Show how to modify the capacities of G to create a new flow network $G_0$ in which any minimum cut in $G_0$ is a minimum cut with the smallest number of edges in G.
I don't understand what the author means by the number of edges in a cut. Does he refer to the edges that leave the cut or lie inside of the cut?
In my case, a cut is defined as $C=(S,T)$ where $V=S\cup T$ and $S\cap T = \phi$, a partition on the set of vertices such that source $s\in S$ and sink $t\in T$.
So, by the number of edges in $C=(S,T)$, does the author mean $\sum\limits_{e\text{ out of } S}1\;\;$?
If this is indeed what the author means, then please read the accepted answer to this: post.
Why does the answerer sets $c(e') = n*c(e) + 1$ when setting $c(e') = c(e) + 1$ does the same job?
For example, given $G=(V,E, c)$ graph with capacity constraints $c$, we want to determine a minimum cut with smallest number of edges.
Then, I transform $G=(V,E,c)$ to $G'=(V,E,c')$ where I set $c'(e) = c(e) + 1 \;\;\forall e\in E$.
Now, any max flow algorithm on $G'$ will minimize $\sum\limits_{e\text{ out of }S \text{ of a }(S,T) \text{ cut }} c'(e) \\=\sum\limits_{e\text{ out of }S \text{ of a }(S,T) \text{ cut }} (c(e) + 1) \\= \sum\limits_{e\text{ out of }S \text{ of a }(S,T) \text{ cut }} c(e) + \text{number of edges leaving } S \\= \text{size of }(S,T) \text{ cut in } G + \text{number of edges leaving } S$
