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

In the great book by Harary and Palmer (Graphical Enumeration) one can find many interesting things about graph asymptotics.

For example it is stated that the number of all unlabeled graph is $\sim 2^{ n \choose 2}/n!$ and that almost all graphs are blocks. They also state that it's very likely that for all natural numbers $n$ almost all graphs are $n-$ connected (do not know if that is already proven or not).

The book is quite old and I assume there are many new results in this field. I am interested in the asymptotics for the number of graphs that are connected but not $2-$ connected. That is connected graphs with more than one block. In the mentioned book I was not able to find any function asymptotic to this quantity but I believe there could be some new result covering my question.

Anyone happens to be aware of it?

share|cite|improve this question
up vote 6 down vote accepted


and references therein (in particular, to the Erdos/Renyi paper).

share|cite|improve this answer

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.