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