Connected graphs that are not 2 connected - MathOverflow 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 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 Answer by Igor Rivin for Connected graphs that are not 2 connected 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>