Karger's min-cut algorithm
/ KAR-ger /
A global minimum cut of a network is the cheapest way to split it into two pieces by removing edges — the fewest cables to cut to disconnect a city into two halves. Finding it exactly sounds like it should need heavy machinery, yet Karger's algorithm finds it with nothing but a startlingly simple idea: repeatedly merge two randomly chosen connected nodes into one, and whatever edges survive at the end form a candidate cut.
Precisely: pick a random edge and 'contract' it, fusing its two endpoints into a single super-node and keeping any parallel edges (but dropping self-loops); repeat until only two super-nodes remain. The edges still joining those two final super-nodes form a cut, and the algorithm outputs it. Why might this be the minimum cut? Fix any one minimum cut C with k edges. The algorithm returns C exactly when it never contracts an edge of C. At each of the n - 2 contraction steps, since the minimum cut has k edges and every node has degree at least k (else a smaller cut exists), the graph has at least nk/2 edges, so the chance of hitting one of C's k edges this step is small; multiplying the survival probabilities across all steps gives Pr[C survives] >= 2 / (n(n-1)), at least about 1/n^2. That is small but not tiny — so run the whole thing O(n^2 log n) times and keep the smallest cut seen, and the probability that you miss the true minimum every single time becomes negligible.
Karger's algorithm matters as a gem of the probabilistic method in action: a one-paragraph randomized procedure solving a problem that classical deterministic methods handle with much heavier flow machinery, and it generalizes (Karger-Stein) to near-O(n^2) time. It also teaches the amplification mindset — a per-run success probability of only 1/n^2 is fine if independent repetition is cheap. The honest caveat: it is Monte Carlo, so a single run is usually wrong; the guarantee only emerges after enough independent repetitions, and you should quote the success probability after amplification, not for one run.
On a graph shaped like two triangles joined by a single edge, the true min-cut is that one bridging edge. Karger contracts random edges; as long as it never picks the bridge to contract, the two triangles collapse into two super-nodes and the surviving bridge is returned — the correct cut of size 1. Pick the bridge early and you get a wrong, larger cut, which is why you repeat.
Random edge contraction returns the min-cut with probability about 1/n^2 per run; repeat to amplify.
A single run succeeds only with probability about 1/n^2, so one run is almost always wrong; the correctness guarantee comes entirely from independent repetition. It is Monte Carlo, and there is no fast way to certify a returned cut is truly minimum, so you cannot cheaply convert it to Las Vegas.