Core Idea - Stoer-Wagner Basics

Stoer-Wagner repeatedly finds a minimum $s$-$t$ cut for specific $s$ and $t$, then merges $s$ and $t$ into a single vertex (contracting them). After $n-1$ merges, you have found the global minimum cut. The algorithm picks $s$ and $t$ based on maximum adjacency: the last two vertices added in a maximum adjacency ordering.

This ordering ensures you do not miss the global min cut across all iterations. Time complexity: $O(n^3)$ with adjacency matrix, or $O(nm + n^2 \log n)$ with a priority queue. Much better than trying all pairs.