MIT
92
Analysis
lEach s-t cut loses f edges, had at least v
lSo, has at
least ( v-f
) / v times as many edges
as before
lBut we increase sampling probability by a
factor of v / ( v-f
)
lSo expected
number of sampled edges no worse than before
lSo Chernoff and
union bound as before