Two days ago it occurred to me that almost all simple graphs are small world networks in the sense that if $G_N$ is a simple graph with $N$ nodes sampled from the Erdös-Rényi random graph distribution with probability half then when $N$ is large:

\begin{equation} \mathbb{E}[d(v_i,v_j)] \leq \log_2 N \tag{1} \end{equation}

My strategy for proving this was to show that when $N$ is large, $\forall v_i \in G_N$ there exists a chain of distinct nodes of length $\log_2 N$ originating from $v_i$ almost surely. This implies that:

\begin{equation} \forall v_i, v_j \in G_N, d(v_i,v_j) \leq \log_2 N \tag{2} \end{equation}

almost surely when $N$ is large.

Now, by using the above method of proof I managed to show that almost all simple graphs are *very small* in the sense that:

\begin{equation} \mathbb{E}[d(v_i,v_j)] \leq \log_2\log_2 N \tag{3} \end{equation}

when $N$ tends to infinity. My question is whether there is an elementary proof that almost all simple graphs are *very small* world networks and if so in what sense are small world networks special?

**Note:** I would consider the probabilistic proof I found elementary though I am not a graph theorist so I am not sure whether it's simpler or more complex than the standard proof.