Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Consider a connected graph $G$ with min-cut $c$. Suppose the edges fail (are removed) independently with probability $p$. Then $U(p)$, the probability that $G$ becomes disconnected, is at least $p^c$. Any such must contain at least $m \geq n c/2$ edges (since the vertices defines cuts).

If we know $U(p) \approx p^c$, can we show $m$ is much larger than this? (For example, if $U(p) = p^c$ exactly, then this means that the min-cut is the only cut and (unless $n = 2$) we have $m = \infty$.)

For example, can we show a bound something like $$ m \geq f( U(p)/p^c ) $$

for some appropriate function $f$?

Thanks for any help!

share|improve this question
Yuichiro, $p^c$ is the probability that the minimum cut gets removed (and the other edges do whatever), which necessarily disconnects the graph. –  David Benson-Putnins May 14 '13 at 3:58
@David Ooh, I got it. I had a brain fart! I should delete the garbage I put there. Thanks! –  Yuichiro Fujiwara May 14 '13 at 4:09
Is $p$ constant, or can it increase with the graph size? The answer surely depends on it. –  Brendan McKay May 14 '13 at 4:52
@Brendan, probably should assume $p^c \approx n^{-\Theta(1)}$. –  David Harris May 15 '13 at 0:50
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.