most recent 30 from http://mathoverflow.net 2013-05-20T19:02:22Z http://mathoverflow.net/feeds/user/23419 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/95849/number-of-connected-components-in-a-graph-from-gn-m Marina 2012-05-03T11:45:49Z 2012-05-07T07:02:58Z

<p>Hello,</p> <p>$G(n,m)$ is the family of all graphs with $n$ vertices and $m$ edges (I consider $m &lt; n$). Each graph in $G(n,m)$ is selected with uniform probability. What is the probability that the graph selected has exactly $c$ connected components?</p> <p>An equivalent question is: what is the probability that exactly $k$ edges should be removed from the selected graph in order to make it a forest (graph without cycles)?</p> <p>There is a solution for the case of $k = 0$ <a href="http://mathoverflow.net/questions/57062/probability-that-a-graph-g-does-not-contain-a-cycle" rel="nofollow">here</a>.</p> <p>Thank you.</p>