Show that at least half of all graphs on n vertices are connected.

Question

I am following a course on Combinatorial Optimization and the question is: Show that at least half of all graphs on n vertices are connected. I have a really hard time understanding and answering questions like this, so any help would be appreciated.

Answer 1

Let $A_n$ be the number of graohs on $n$ vertices and $B_n$ the number of connected such graphs, and $C_n:=\frac{B_n}{A_n}$. The claim is that $C_n\ge\frac 12$.

Clearly, $A_n=2^{n-1}A_{n-1}$ (a graph on $n$ vertices is obtained from a graph on $n-1$ vertices by perhaps adding edges from vertex $n$ to other vertices). Similarly, $$B_n\ge (2^{n-1}-1)B_{n-1}$$ (at least one edge from vertex $n$ to a connected graph on $n-1$ vertices produces a connected graph). Hence $C_n\ge\left(1-\frac1{2^{n-1}}\right)C_{n-1}$ -- which is unfortuneatle not yet good enough: From $C_1=1$, we find from this $C_2\ge\frac12$, but only $C_3\ge \frac38$. A manual count gives us the correct value $C_3=\frac12$.

For $n\ge 4$, we can also obtain a connected graph by

• picking one of the old $n-1$ vertices and connecting vertex $n$ to it
• picking a connected graph on the remaining $n-2$ $(>1)$ vertices
• adding at least one of the edges from $n$ to this

in $(n-1)\cdot(2^{n-2}-1)\cdot B_{n-2}$ ways.

This gives us the better bound $$B_n\ge(2^{n-1}-1)B_{n-1}+(n-1)\cdot (2^{n-2}-1)B_{n-2}\qquad\text{for }n\ge 4. $$ So for $n\ge 4$, $$ \begin{align}C_n&\ge\frac{(2^{n-1}-1)B_{n-1}}{2^{n-1}A_{n-1}}+\frac{(n-1)(2^{n-2}-1)B_{n-2}}{2^{n-1}2^{n-2}A_{n-2}}\\ &=\left(1-\frac1{2^{n-1}}\right)C_{n-1}+\frac{n-1}{2^{n-1}}\left(1-\frac1{2^{n-2}}\right)C_{n-2}\\ &>\left(1-\frac1{2^{n-1}}\right)\cdot \frac12+\frac1{2^{n-1}}\cdot \frac12\\ &=\frac12\end{align}$$ and the claim follows by induction.