Stoer-Wagner Algorithm

The Stoer-Wagner algorithm finds the global minimum cut in $O(n^3)$ time. It works by repeatedly finding minimum $s$-$t$ cuts for carefully chosen $s$ and $t$, then merging vertices. The algorithm contracts the graph by merging vertices and tracking cut weights.

After $n-1$ iterations, you have checked enough cuts to find the global minimum. This is the standard approach for global minimum cut in undirected graphs.

Space complexity is $O(V + E)$ for the data structures used.