• Overview and Definitions
• Cut and Cycle Properties
• Stoer–Wagner Global Min-Cut
• Variants and Related Algorithms
• Pitfalls
• Exercises

• Cut (S, V\S): Sum of weights of edges crossing from S to its complement.
• Global min-cut: Minimum cut over all nontrivial partitions of V in an undirected weighted graph.
• Not MST-specific: Cut/cycle properties underlie greedy MST proofs; min-cut seeks a smallest edge boundary.

• Cut property: For any cut, the lightest edge crossing it is in some MST.
• Cycle property: For any cycle, the heaviest edge is in no MST.
• Exchange argument: Swapping edges maintains acyclicity/connectivity while not increasing weight.

// Stoer–Wagner min-cut for undirected weighted graphs
// Input: n, adjacency matrix or adjacency list with symmetric weights
// Here we use adjacency matrix w[n][n] (0 on diagonal), modify on contractions.
function stoerWagnerMinCut(w) {
  const n = w.length;
  const vertices = Array.from({length: n}, (_, i) => i);
  let best = Infinity;
  const used = Array(n).fill(false);

  for (let phase = 0; phase < n - 1; phase++) {
    const A = Array(n).fill(false);
    const weights = Array(n).fill(0);
    let prev = -1, sel = -1;

    for (let i = 0; i < n - phase; i++) {
      sel = -1;
      for (let v = 0; v < n; v++) if (!used[v] && !A[v]) {
        if (sel === -1 || weights[v] > weights[sel]) sel = v;
      }
      if (i === n - phase - 1) {
        // Last added: defines a cut with previous selected node
        best = Math.min(best, weights[sel]);
        // Contract sel into prev
        if (prev !== -1) {
          for (let v = 0; v < n; v++) if (!used[v] && v !== prev) {
            w[prev][v] += w[sel][v];
            w[v][prev] = w[prev][v];
          }
          used[sel] = true;
        }
        break;
      }
      A[sel] = true; prev = sel;
      for (let v = 0; v < n; v++) if (!used[v] && !A[v]) weights[v] += w[sel][v];
    }
  }
  return best;
}

• Idea: Repeated "maximum adjacency search" phases; last two added vertices induce a min s–t cut. Contract and repeat.
• Complexity: O(n^3) with matrices; O(nm + n^2 log n) with heaps and adjacency lists.
• Output: Value of global min-cut. To recover the partition, track supernodes during contractions.

• Karger/Karger–Stein: Randomized contraction, near-linear expected time; repeated runs increase success probability.
• s–t min-cut: In directed graphs equals max flow via max-flow min-cut theorem.
• Edge vs. vertex cut: Vertex cuts can be reduced to edge cuts by vertex splitting.

• Ensure symmetry of weights for undirected graphs.
• Handle multi-edges during contraction by summing weights.
• For large sparse graphs, prefer adjacency lists + heap optimization.

1. Implement Stoer–Wagner using adjacency lists with a max-heap and test on random weighted graphs.
2. Recover an explicit min-cut partition by tracking supernodes through contractions.
3. Compare Stoer–Wagner vs. repeated Karger–Stein on large sparse graphs.