Does a Given Network has a Unique Min-Cut?

Question

Let G = (V, E) be a network with s and t being the source and the sink. Let f be a maximum flow in G. Find an algorithm that determines whether there exists a unique min-cut in G.

I have managed to find a similar question on this site:

Determining the uniqueness of a min-cut

A summary of the answer given there:

Find all the vertices reachable from s in the residual graph and we've found a min-cut (S,T) in G.

Look at the same residual graph, starting at t. Look at the group of vertices reachable from t in the reverse direction of the arrows (meaning all the vertices which can reach t).

This group is also a min-cut.

If that cut is identical to your original cut, then there is only one. Otherwise, you just found 2 cuts, so the original one can't possibly be unique.

I don't understand why if the cut is identical to the original cut then the cut is unique. Who can promise us that there is no other min-cut ?

Thanks in advance

Answer 1

Actually, I don't quite understand that solution. But in the original question, the second answer provided by davin is absolutely correct.

I just copy and paste it here

Given a minimum S-T cut, (U,V) with cut-edges E', we make one simple observation:
If this minimum cut is not unique, then there exists some other minimum cut with 
a set of cut-edges E'', such that E'' != E'.

If so, we can iterate over each edge in E', add to its capacity, recalculate the
max flow, and check if it increased.

As a result of the observation above, there exists an edge in E' that when
increased, the max flow doesn't increase iff the original cut is not unique.

some explanation of my own:

What you need to prove actually is

there exists an edge in E' that when increased, the max flow doesn't increase
<=>
the original cut is not unique

=>:
You increase the capacity of edge e by 1, calculate the new max flow and it remains the same, which means that e is not in the new min-cut. (if e is in, according to the property of min-cut, f(e)=capacity of e, which leads to an increase). Since e is not in the new min-cut, it is also a min-cut of the original graph which has the same volume with the cut we know.Thus, the original cut is not unique.

<=:
The original cut is not unique(Let's call them E and E'), which means you can find an edge e that is in E but not in E'. Then you just increase the capacity of e by 1. When calculating the min-cut of the new graph, E' is already there. Since E' doesn't contain edge e, max flow remains the same with no doubt.

Hope you understand :)

Answer 2

another option to prove by contradiction the first way: ->: let's say there's a single minimal (S,T) cut with cut edges E'. After increasing the capacity of edge e which belongs to E' by 1 and finding that the max flow remains the same, leads that e is not in the new min-cut. (if e is in E', according to the property of min-cut the max flow would be increased). However at the beginning we said the e is in E' - contradiction