MIT
113
Proof of Theorem
l
Given
p
c
=
1
/
n
(2+
d
)
l
At most
n
2
a
cuts have value
a
c
l
Each fails with probability
p
a
c
=
1
/
n
a
(2+
d
)
l
Pr[any cut of value
a
c
fails] =
O
(
n
-a
d
)
l
Sum over all
a
> 1
