# Min cut with smallest number of edges [duplicate]

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$$

• The cut is the edges that go from $S$ to $T$, that is, leaving $S$. They want you to find a minimum cut with as few edges as possible. Commented Dec 9, 2021 at 14:09
• @PålGD Thank you for clarifying that, and yes it does. Commented Dec 9, 2021 at 14:22