Stoer-Wagner repeatedly finds a minimum - cut for specific and , then merges and into a single vertex (contracting them). After merges, you have found the global minimum cut. The algorithm picks and 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: for an unweighted graph, for weighted graphs. Much better than trying all pairs.