 |
 |
12 of 32 |  |
 |
 |
MIT
Analysis I
l
Min-cut is small---few edges
»
Suppose graph has min-cut ©
»
Then minimum degree at least c
»
Thus at least nc/2
edges
l
Random
edge is probably safe
Pr[min-cut edge] £
c/(nc/
2)
= 2/
n
(easy generalization to capacitated case)