Minimum Cuts in Near-Linear Time

Strength Lemma

Lemma: å 1/c_e £ n

Consider connected component C of G

Suppose C has min-cut k

Then every edge e in C has c_e ³ k

So k edges crossing C’s min-cut have

å 1/c_e £ å 1/k £ k (1/k ) = 1

Delete these edges (“cost” 1)

Repeat n - 1 times: no more edges!