3

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!

athul777
  • 639
  • A graph is connected iff its complement is disconnected, hence if "random" here means that we take (or not) any edge of $K_n$ with probability $\frac{1}{2}$, a random graph is connected with probability $\frac{1}{2}$, not $1$. – Jack D'Aurizio Jun 02 '16 at 01:01
  • Thanks for your answer! But I'm not quite sure what you mean when you say "take any edge of $K_n$ with probability $\frac{1}{2}$" and I'm not sure where I implied that a random graph is conneced with probability 1? Would you please explain further? Thanks again! – athul777 Jun 02 '16 at 01:35
  • 1
    There are different models of random graph. A possible model is to take every edge of $K_n$ (the complete graph on $n$ vertices) with probability $\frac{1}{2}$. Since some graph and its complement have the same probability to have been chosen, a random graph in this model is connected with probability $\frac{1}{2}$. – Jack D'Aurizio Jun 02 '16 at 01:41
  • Ah, that makes sense, thank you! So which random model would I have to construct such that almost every one of these random graphs is connected? – athul777 Jun 02 '16 at 01:55
  • A more flexible model is the random dot product model (https://en.wikipedia.org/wiki/Random_graph). – Jack D'Aurizio Jun 02 '16 at 02:02
  • @JackD'Aurizio Actually, the statement about a graph being connected if and only if its complement is disconnected is actually not correct. Therefore your answer (1/2) cannot be correct. I think the correct statement is a graph is connected if and only if its complement is bipartite. – athul777 Jun 02 '16 at 21:55
  • http://math.stackexchange.com/questions/122184/given-a-simple-graph-and-its-complement-prove-that-either-of-them-is-always-con – Jack D'Aurizio Jun 02 '16 at 21:56
  • Or, simply: take a cycle on $7$ vertices. It is obviously connected, and its complement is not bipartite. – Jack D'Aurizio Jun 02 '16 at 21:59
  • Oh, I'm sorry, I meant to say a graph is not connected if and only if its complement is bipartite – athul777 Jun 02 '16 at 22:01
  • Then take three disjoint cycles on $7$ vertices. That is not a connected graph and its complement is not bipartite. – Jack D'Aurizio Jun 02 '16 at 22:02
  • I suggest you to follow the link above before further discussions. – Jack D'Aurizio Jun 02 '16 at 22:03
  • There is also a nice post on MO (with a great answerer): http://mathoverflow.net/questions/60075/connectivity-of-the-erd%C5%91s-r%C3%A9nyi-random-graph – Jack D'Aurizio Jun 02 '16 at 22:06
  • 1
    @JackD'Aurizio This is obviously false. You can see examples in https://en.wikipedia.org/wiki/Self-complementary_graph The link you gave proves that if $G$ is disconnected, then its complement is connected, not the converse! – Graffitics Jul 06 '16 at 10:32

1 Answers1

5

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.

Graffitics
  • 1,508