User marina - MathOverflow 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 Number of connected components in a graph from G(n,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>