# Randomized algorithm for minimum cut

Given a simple undirected connected graph $$G$$, I want to find a min-cut of $$G$$ using a randomized algorithm.

My attempt was to select a random edge in $$G$$ and reduce that edge to a single vertex. And recursively do it until the number of vertices is at most 2.

The number of edges present (in the resulting multi-graph) will be the min-cut. This is the standard algorithm I found at many places.

Will this lead to the exact number of min-cut and how can I extract the vertices on each side of the cut?

• If the number of vertices is 2, wouldn't you be left with at most one edge? I don't understand why this approach will calculate the min-cut Apr 8, 2021 at 8:39