6
$\begingroup$

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.

  • 0
    The problem statement is unclear to me. I don't see how the two cases exhaust all possibilities. There are connected graphs with 5 edges and 6 edges as well. Or perhaps your case 2 is the complete graph, in which case there's a connected graph with only 3 edges that is missed.2012-04-01
  • 0
    i edited the question. apologies for the ambiguity in the question... we stop adding edges once we have a connected graph...2012-04-01
  • 2
    The paper you cite prove $(n-1)H_{n-1}$ as an upper bound for the expectation, not the expectation itself.2012-04-01

2 Answers 2