MIT
17
Analysis I
lMin-cut
is small---few edges
»Suppose
graph has min-cut c
»Then
minimum degree at least c
»Thus
at least nc/2 edges
lRandom edge is probably
safe
lPr[min-cut edge] £ c/(nc/2)
= 2/n
l(easy generalization to capacitated case)