Exact probability of random graph being connected

Solution 1:

Here is one way to view the formula. First, note that it suffices to show that $$ \sum_{i=1}^n {n-1 \choose i-1} f(i) (1-p)^{i(n-i)} = 1, $$ since ${n-1 \choose n-1}f(n)(1-p)^{n(n-n)}=f(n).$ Let $v_1, v_2, \ldots, v_n$ be $n$ vertices. Trivially, $$ 1= \sum_{i=1}^n P(v_1 \text{ is in a component of size }i). $$ Now let's consider why $$P(v_1 \text{ is in a component of size }i)={n-1\choose i-1}P(G(i,p) \text{ is connected}) (1-p)^{i(n-i)}.$$ If $\mathcal{A}$ is the set of all $i-1$ subsets of $\{v_2, v_3, \ldots, v_n\}$, then \begin{align*} P(v_1 \text{ in comp of size }i)&=\sum_{A \in \mathcal{A}}P(\text{the comp of }v_1\text{ is }\{v_1\}\cup A)\\&=\sum_{A \in \mathcal{A}}P(\{v_1\}\cup A \text{ is conn'd})P(\text{no edge btwn }A\cup\{v_1\} \& \ (A\cup \{v_1\})^c). \end{align*} This last equality is due to the fact that the edges within $\{v_1\}\cup A$ are independent of the edges from $A$ to $A^c$. There are precisely ${n-1 \choose i-1}$ elements in $\mathcal{A}$. The probability that $\{v_1\}\cup A$ is connected is equal to the probability that $G(1+|A|,p)$ is connected, which is $f(i)$. There are $i(n-i)$ missing edges from $\{v_1\}\cup A$ to $(\{v_1\}\cup A)^c$.

Solution 2:

What happens is that he/she sums over all cuts of the graph. To avoid counting anything twice, you focus specifically on some specific vertex, calling it $1$.

If the graph is disconnected, there is going to be a connected component of some size, which contains $1$.

So you sum over the size this component might have, and with multiplicity $n-1 \choose i-1$ which is the number of ways to choose $1$'s fellow set members. You want the component containing $1$ to be connected, so you multiply by $f(i)$, but nothing in the component can be connected to something not there, so you multiply by $(1-p)^{i(n-i)}$. The $(n-i)$ part of the graph can be connected or not, it doesn't matter.

A slight problem with the formula is, that it is not stable for small $p$s and large $n$s.