most recent 30 from http://mathoverflow.net 2013-05-22T11:13:56Z http://mathoverflow.net/feeds/question/58836 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/58836/connected-graphs-that-are-not-2-connected Jernej 2011-03-18T13:13:11Z 2011-03-18T13:19:15Z

<p>In the great book by Harary and Palmer (Graphical Enumeration) one can find many interesting things about graph asymptotics. </p> <p>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).</p> <p>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.</p> <p>Anyone happens to be aware of it?</p>

http://mathoverflow.net/questions/58836/connected-graphs-that-are-not-2-connected/58837#58837 Igor Rivin 2011-03-18T13:19:15Z 2011-03-18T13:19:15Z

<p>See</p> <p><a href="http://www.math.uwaterloo.ca/~nwormald/papers/2connected.pdf" rel="nofollow">http://www.math.uwaterloo.ca/~nwormald/papers/2connected.pdf</a></p> <p>and references therein (in particular, to the Erdos/Renyi paper).</p>