Find a minimum cardinality subset of edges to disconnect a graph.
Contract a random edge.
While there are more than two vertices in the graph, choose a uniformly random edge uv and contract the two endpoints. Output the edges between the remaining two vertices.
Theorem: Success probability of returning a min-cut is at least \frac{2}{n(n-1)}.
Let F \le E be a minimum cut, say |F| = k. The probability that we don’t choose an edge in F in the i-th iteration is \frac{|F|}{|E|}. In the i-th iteration, we have (n - i + 1) vertices. The minimum cut is assumed to be at least k, so the minimum degree is also at least k, so the number of edges is at least \frac{(n - i + 1) k}{2}. So probability for the i-th iteration is upper-bounded by \frac{2}{n - i + 1}
Probability of success in all iteration.
\Pi_{i=0}^{n-3}\left(1 - \frac{2}{n-i}\right) = \frac{n-2}{n} \cdot \frac{n-3}{n-1} \cdot \frac{n-4}{n-2} ... = \frac{2}{n(n-1)}
Let us repeat T many times, taking the best result. The failure probability is now \left(1 - \frac{2}{n(n-1)}\right)^T \le e^{\frac{-2T}{n(n-1)}}.