# # bridges in random connected graph

Suppose we have an Erdos random graph with $n$ vertices and $c n$ edges.

What can you say about the probability that the graph is connected?

(More importantly) If it is connected, what is the distribution on the number of bridges?

EDIT:

I am interested in asymptotics as $c$ is fixed but $n \rightarrow \infty$. That is, I know that the probability that the graph is connected is exponentially small in $n$, but I don't know what the exponent is.

As for the number of non-bridges, I would like some result like the number of bridges for a random connected graph is $> c' n$ where $c'$ is another constant, with probability approaching $1$.

-
If $c$ is a fixed constant, then almost surely the graph will contain isolated vertices and hence be disconnected. Indeed it is well-known that $p=\log(n)/n$ is a sharp threshold for connectivity of $G(n,p)$. –  Tony Huynh Jun 13 '11 at 16:04
@David: From the title (I cannot access the paper), this seems promising for the asymptotics of connectivity, or, at the least, useful citations: Robert F. Ling, "An exact probability distribution on the connectivity of random graphs." Journal of Mathematical Psychology, Volume 12, Issue 1, February 1975, Pages 90-98. –  Joseph O'Rourke Jun 13 '11 at 16:43

Concerning your first question, if $p$ is the edge probability, then $G(n,p)$ is almost surely connected when $p$ passes the sharp $\ln n/n$ threshold. Because $G$ has about $p \binom{n}{2}$ edges, which in your formulation is $c n$, when $c$ exceeds $c_t=((n-1)/ (2n)) \ln n$, then $G$ is almost surely connected, and below that, will almost surely be disconnected. So if you fix $c$ and let $n \rightarrow \infty$, the threshold $c_t$ grows without bound and your fixed $c$ will be below it, and so $G$ almost surely disconnected.
The number of isolated vertices has expected value approximately $n e^{-2c}$, so the probability that there are no isolated vertices should be approximately $e^{-n e^{-2c}}$. This should be an upper bound on the probability of connectedness. Better approximations should be attainable by taking into account other ways a graph can be disconnected, e.g. having two vertices connected only to each other.
When c=1, this estimate gives $e−(n∗e−2))≈1.14^{−n}$ while Cayley's formula gives $1.36^{−n}$. So this bound is not tight. –  David Harris Jun 13 '11 at 19:49