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

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?


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

share|cite|improve this question
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.

share|cite|improve this answer
Oh, Tony's comment with the same content appeared as I was writing this! – Joseph O'Rourke Jun 13 '11 at 16:23

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.

share|cite|improve this answer
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

Your Answer


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

Not the answer you're looking for? Browse other questions tagged or ask your own question.