# Prove that Ford-Fulkerson can decide if there is more than one min cuts

Probelm: Deciding whether a network flow graph has more than one min cut.

Optimal running time: O(V^2*E).

I trying to prove the correctness of the next algorithm: run Dinitz to find max-flow and build the residual graph. One min cut will be all the vertices reachable from s (as T will be all other vertices) and second min cut will be all vertices reachable from t in the reverse graph. If both cuts are equal, than there is only one min cut. Otherwise, there are more.

I'm struggling proving this algorithm. I cannot find a reason for ensuring that I'll find another min cut if it exists. I tried to prove a lemma saying that a network flow graph has a unique minimum cut, iff each vertex is reacable from s or t in the residual graph. But I'm stuck proving the <= direction.

• possible duplicate of Does Ford-Fulkerson always produce the left-most min-cut – D.W. Jun 5 '15 at 4:34
• This is not a duplicate, I need a formal prove, which I cannot find. – user3680924 Jun 5 '15 at 5:26
• What have you tried and where did you get stuck? (Also, keep in mind that nobody here is obligated to give you a full, formal proof. A proof roadmap may be the best you can get.) – Raphael Jun 5 '15 at 5:59
• I'll let others judge if it's a dup. You asked "how do I know that the first method is correct?" The results at the link I gave immediately yield a satisfying answer to your question. It has all the ideas needed for you to write your own full, formal proof. Work through the details there, then try seeing what you can come up with on your own. If you're still stuck edit the question to show us your attempt and what you're stuck with; if that's enough for you to figure it out, you can accept the duplicate or write up the full formal proof and list it as a self-answer to this question. – D.W. Jun 5 '15 at 6:19
• Raphael - I thought about proving a lemma: in a network flow graph, there is unique minimum cut if and only if in the residual graph of the maximum-flow, each vertex is reachable from s or t (by reversing the edges). I can prove one side, by saying that if there is at least one vertex that is not reachable from both s and t, then by finding all reachable vertices from s in the first time and from t in the second time, I will receive two different minimum cuts, in contrary to the assumption that there is only one. But I can't prove the other side, I'm stuck. – user3680924 Jun 5 '15 at 6:51

Perhaps it would be helpful for you to recall properties of the min-cut that is produced by applying the min-cut/max-flow theorem to the flow output by a max-flow algorithm. In particular, define $S$ to be the set of vertices reachable from $s$ along some path in the residual graph, and $T$ to be the set of vertices that can reach $t$ along some path in the residual graph. Then $S \cap T = \emptyset$ and $S \cup T = V$, and $(S,T)$ is a $(s,t)$-cut. In particular, $(S,T)$ is the cut that is selected by the min-cut/max-flow theorem (for this flow). Good.
Now notice that $T$ is exactly the set of vertices that are reachable from $t$ in the reverse of the residual graph. Therefore, your proposed algorithm amounts to finding a max-flow, computing the sets $S$ and $T$, then checking whether $S$ and $T$ are the same cuts. But the only way to interpret $S$ as a cut is as the cut $(S,V\setminus S)$, and the only way to interpret $T$ as a cut is as the cut $(V\setminus T, T)$ -- and these are always exactly the same cut! In particular, $V \setminus S = T$ and $V \setminus T = S$, so both of these cuts will always be exactly the same cut -- even if the flow graph admits multiple different cuts, your procedure will only find one of them.
• @user3680924, 1. If you don't understand why it fails, I encourage you to pick an example graph with two or more min cuts, run your algorithm on it (by hand), and add this to the question (add the graph & add the results you get). 2. My answer does not refer to the concept "left-most min-cut", but if you want to know the definition, see the links I gave you earlier in the comments (cs.stackexchange.com/q/42960/755 and stackoverflow.com/q/29418244/781723) -- in particular, if $(S_1,T_1),\dots,(S_n,T_n)$ are a list of all min-cuts, the left-most is $(\cap_i S_i, \cup_i T_i)$. – D.W. Jun 10 '15 at 18:30