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.

  • $\begingroup$ 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. $\endgroup$ – Patrick Apr 1 '12 at 17:53
  • $\begingroup$ i edited the question. apologies for the ambiguity in the question... we stop adding edges once we have a connected graph... $\endgroup$ – John Smith Apr 1 '12 at 17:57
  • 2
    $\begingroup$ The paper you cite prove $(n-1)H_{n-1}$ as an upper bound for the expectation, not the expectation itself. $\endgroup$ – Greg Martin Apr 1 '12 at 19:16

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.


Let $P$ be the set of $n(n-1)/2$ potential edges (unordered pairs in ${1,\ldots,n}$). For each $S \subseteq P$ let $A(S)$ be the expected number of edges to add, starting with the graph with set of edges $S$, until you obtain a connected graph. Thus $A(S) = 0$ iff the graph with edges $S$ is connected, and otherwise $$A(S) = 1 + \sum_{e \notin S} A(S \cup \{e\})/(n(n-1)/2 - |S|)$$ The answer you want is $A(\emptyset)$. Of course this is not going to be practical to compute if $n$ is large.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.