Question

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$.

Answer 1

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.

Answer 2

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.