Edge & Vertex Connectivity — Stoer–Wagner Global Min-Cut

The Stoer–Wagner algorithm finds the global minimum cut without max-flow. Each phase grows a set A by repeatedly absorbing the most tightly connected vertex (maximum adjacency). The last two vertices added are s and t; the cut isolating the last one is a minimum s-t cut. Then s and t are merged and the next phase begins. The smallest cut over all phases is the global min-cut.