Proof of Theorem
l Given pc=1/n(2+d)
l At most n2a  cuts have value ac
l Each fails with probability pac=1/na(2+d)
l Pr[any cut of value ac fails] = O(n-ad)
l Sum over all a > 1