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.

  • 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

1

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.

1

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.