MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

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.