So, I'm trying to show that a random graph is almost surely connected.
I want to know if my intuition is correct, and if so, how to formalize that intuition into a proof. If a graph $G=(V,E)$ has $|V|=n$, and it is disconnected, then it has at least 2 components. Let us arbitrarily divide the vertices into 2 subsets $U, W \subseteq V$ such that $|U|=k$ and $|W|=n-k$ such that $U$ and $W$ are connected. Then for $G$ to be disconnected, no vertex in $U$ can be connected to any other vertex in $W$. Therefore the probability that none of the vertices between $U$ and $W$ are connected is $(\frac{1}{2})^{k(n-k)}$, and since $k(n-k) \leq \frac{n^2}{4}$, $P \leq (\frac{1}{2})^{\frac{n^2}{4}})$, and when $n$ is large, this probability tends to 0, making the graph almost always connected for a random graph.
If this intuition is correct, how do I formalize it for all possible configurations of $U$ and $W$? Any help would be thoroughly appreciated!
Best Answer
Here, random graph means $\mathcal{G}(n,1/2)$. As $n$ goes to infinity, any graph sampled from $\mathcal{G}(n,1/2)$ is almost surely connected (the probility that it is connected goes to $1$, and pretty quickly).
There is actually a very simple argument, you can show it by showing that any pair of vertices has a common neighbor. Let's estimate the probability that the previous statement is false. There are ${n \choose 2}$ pairs of vertices, and each one can find a witness among $(n-2)$ vertices. Each of these vertices is not a witness if at least one edge is missing, which means probability $3/4$. Putting everything together, the statement fails with probability ${n \choose 2} \times (3/4)^{(n-2)} \rightarrow 0$, which means that it almost surely holds.