MIT
29
Cut Counting
lOriginal
CA finds any given min-cut with probability at least 2/n(n-1)
lOnly
one cut found
lDisjoint
events, so probabilities add
lSo
at most n(n-1)/2 min-cuts
»probabilities
would sum to more than one
lTight
»Cycle
has exactly this many min-cuts