# Number of edges in graph in terms of reliability

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!

-
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