Let $E^c\_n$ be the expected number of connected components of a simple undirected graph on the vertex set $\{1,\ldots,n\}$. (Every possible edge in $\big\{\{a, b\}: a, b\in \{1,\ldots,n\} \land a \neq b\big\}$ is picked with probability $1/2$.)


Is $\{E^c\_n: n\in\mathbb{N}\}$ bounded? If yes, what is the least upper bound, and if no, do we have $\lim \sup\_{n\to\infty}\frac{E^c\_n}{n} = 0$?



Expected number of connected components as $V(G)$ grows large
$E\_{n+1}^c \leq E\_n^c + \frac{1}{2^n}$, so as $E\_0^c = 0$, we have that $E\_n^c \leq 2$.


Reason: For a graph $G$, define $|G^c|$ as the number of components of $G$. Then for any labeled graph $G$, there are $2^n$ graphs with $n + 1$ vertices such that the subgraph on the first $n$ vertices is $G$. The one such that none of those "new" edges exists has exactly 1 more component, while the rest have at most as many components as $G$.


The case where the edge probability decreases proportional to $\frac{1}{n}$ seems to be more studied; according to Wikipedia (<https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93R%C3%A9nyi_model>), "Almost every graph in G(n, 2ln(n)/n) is connected", so in fact the limit should be 1.


