Expected number of Edges required to make a graph

问题:

We select two vertices randomly and connect them. So what is the expected number of edges in the graph when it becomes connected ?

I tried solving it using induction but couldn't reach to an answer. What will be the right approach to this problem ?

回答1:

For given number of vertices n and chosen count of edges, you get the probability of the graphs connectedness as the proportion of connected graphs to all graphs.

Number of all graphs is the combination number of m over n * (n - 1).

Asymptotic formula for number of connected graphs is given in The asymptotic number of labeled connected graphs with a given number of vertices and edges by Edward A. Bender, E. Rodney Canfield, Brendan D. McKay (don't ask me to explain it :-) )

Last, you have to specify what you mean by "expected number" - you have to choose a probability threshold (like 95%) and search for an m where this formula gives a probability higher than this threshold.