 |
 |
 |
 |
 |
 |
 |
 |
 |
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
|
|