Imagine a simple undirected graph with a countably infinite number of vertices, each labeled with an unique integer $v \in \mathbb{Z}$. Connect the vertices by edges randomly such that
- Each vertex has at least two edges
- The average number of edges a vertex has is $2+\epsilon$ where $\epsilon \in [0,\infty)$
What (if any) is the minimum $\epsilon$ such that the entire graph is connected? I have a vague hypothesis that the answer is $\epsilon>0$.
Given a large connected graph, by definition it's number of edges are maximized when it is complete, in this case, every complete graph with $n$ vertices has $n-1$ connections. Consider a disconnected graph with several mutually exclusive connected subgraphs. It's a natural extension that the maximal number of edges for this graph will be when all it's subgraphs are complete.
Consider a disconnect graph which consists of two disjoint complete subgraphs, $K_{N-l}\cup K_l$ which have a total of $N$ vertices.
Since a requirement is that every node has $2$ or more edges, $N-2>l>2$.
In this case, the mean number of edges per node is $$E[e] =\frac{(N-l)(N-l-1) + l\cdot(l-1)}{N} = N - (2l + 1) + \frac{2l^2}{N}$$ If we consider maximizing this as a function of $l$ we can find a lower boundary of $\epsilon_N$. $$\frac{\partial E[e]}{\partial l} = \frac{4l}{N} -2, \ \ \frac{\partial^2}{\partial l^2}E[e] = \frac{4}{N} > 0$$ So we know that $\frac{\partial E[e]}{\partial l} = 0 \implies l = \frac{N}{2}$ is a global minimum, and $E[e]$ is maximized when $l\in\{3, N-3\}$.
Because of this, it must be required that there must be more than $N - 7 + \frac{18}{N}$ edges before concluding definitively that the graph is connected.
Thus, for any graph with a finite mean number of edges per node, there are graphs which exist such that their expected number of edges per node is larger while still being disconnected.