Minimum-cut with minimum number of edges

Question

I am sure many folks here know the famous min-cut max-flow theorem - the capacity of the minimum cut is equal to the maximum flow from a given source, s, to a given sink, t, in a graph.

Firstly, let's state (for completeness) that an s-t cut is the partitioning of the vertices in the graph, into two parts, such that the source s is in one partition and the sink t is in the other. The cut-set is the set of edges that are going from vertices in the partition that contains s to those in the other partition.

There may be multiple s-t cuts that have the same capacity as the min-cut (with different sized cut sets). The problem that I wish to solve is, how to find the minimum s-t cut that also has the minimum size cut set?

For example, in the following graph where s = 0 and t = 4:

We can clearly see that the capacity of the minimum cut is 2. One possible way to get this is to take edges 0-2 and 1-3 (This cut set has size 2). Another possible way to do this is to take edge 3-4 instead (This cut set has size 1) which is the optimal answer.

I have researched about this question and some people are saying that we need to transform the edge capacity, C, of every edge to C * (|E| + 1) - 1, where |E| is the number of edges in the graph.

One such discussion here: https://codeforces.com/blog/entry/51748
Another such discussion here: https://stackoverflow.com/questions/38408852/finding-the-lowest-amount-of-edges-in-all-minimum-cuts-in-flow-network

The problem is, I don't understand why this formula works. In particular, why do we need to multiply by (|E| + 1) and not some other number? I cannot see how multiplying by any other number would "change" the augmenting paths in the graph as stated in the cited links.

Could someone please advise me?

Edit: The offset in the formula should be +1 and not -1 in order to get the cut-set of the smallest size.

Answer 1

Those answers assume that all edge capacities are integers. Assuming they are, this works.

Suppose the min-cut in the original graph has total capacity $x$; then it will have total capacity $x(|E|+1)+k$ in the transformed graph, where $k$ counts the number of edges crossing that cut. Note that if you consider any cut in the original graph with larger capacity, its original capacity will be $x+1$ or more, so its total capacity in the transformed graph will be $(x+1)(|E|+1)+k'$ for some $k'$ in the range $0 \le k' \le |E|$. Now

$$\begin{align*} (x+1)(|E|+1)+k' &= x(|E|+1)+|E|+1+k'\\ &> x(|E|+1)+|E|\\ &\ge x(|E|+1)+k, \end{align*}$$

so any cut in the original graph that isn't a min-cut won't be a min-cut in the transformed graph, either.

In other words, any min-cut of the transformed graph will be a min-cut of the original graph.

Moreover, out of all of the min-cuts in the original graph, the one whose cut set is smallest is the one that will have lowest capacity in the transformed graph (since the transformation adds one for each edge in the cut set). So, the min-cut in the tranformed graph will be a min-cut in the original graph, and it will break ties by choosing the one with smaller cut set.