There are n vertices. 2 vertices are chosen such that there is no edge between them and add an edge between them. We choose each pair with equal probability. Once we a have a completely connected graph we stop adding edges. Let X be the number of edges before we obtain a connected graph. What is the expected value of X?
For example, when number of vertices are 4
case 1:> 3 edges form a triangle, and we need a 4th edge to make the graph completely connected.
case 2:> all the 4 nodes are connected by 3 edges.
The probability of the case 1 is 4/20 (number of triple of edges that make a triangle divided by number of ways we can choose 3 different edges), and the probability of case 2 is 16/20. So the expected value would be 4/20*4 + 16/20*3 = 3.2
I looked through http://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93R%C3%A9nyi_model to get the answer. However, I did not get a clue.
I also looked through http://www.cs.berkeley.edu/~jfc/cs174/lecs/lec9/lec9.pdf
there it was shown that expected value is (n-1)*((n-1)st Harmonic number).
Using that for n=4 we get 3 * 1.83 = 5.5
But, the answer I am looking for is 3.2.
Now, is there a mathematical formula to get the answer directly? Please show me the way. I am a noob in math.
Edit1: The number of edges we need to consider is (n-1) to (n-1)(n-2)/2. The minimum number of edges in a connected graph is (n-1). The maximum for this question is (n-1)(n-2)/2 + 1. This is because (n-1) edges can be connected by maximum (n-1)(n-2)/2 edges, and 1 edge to connect to the lonely vertex.
Best Answer
The probability that a Bernoulli random graph (see page 4) with $pn^2/2$ edges is connected is about $1-n(1-p)^n$. So if $p$ is a huge multiple of $(\log n)/n$, then the probability is very close to 1. To me this suggests that the expected number of edges needed to make the graph connected does indeed have order of magnitude $n\log n$. But this is of course not an exact formula.