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. 



Almost all simple graphs are small world networks

> 
> whether there is an elementary proof that almost all simple graphs are very small world networks
> 
> 
> 


Following up on Brendan McKay's comment. The chance that an Edos-Renyi$(0.5,n)$ graph has diameter one is $0.5^{n(n-1)/2}$, which of course goes to zero exponentially fast.


On the other hand, two vertices have a distance of at most two if there exists a third vertex with edges to both of them. For a fixed third vertex, this chance is $0.5^2 = 1/4$. By independence, the chance this fails to occur for all $n-2$ choices of third vertex is $(3/4)^{n-2}$.


There are $n(n-1)/2$ pairs of vertices, so by a union bound, the chance that there exists a pair of distance strictly more than $2$ is at most
 $$ \frac{n(n-1)}{2} \left(\frac{3}{4}\right)^{n-2} .$$


So the diameter of the graph is $2$ with probability $1 - e^{-\Theta(n)}$.



> 
> if so in what sense are small world networks special
> 
> 
> 


Of course people more expert than I can go on about it at length. But (1) networks arising in Euclidean space, like road networks, don't have these kinds of properties. And many of our networks, even social networks, are roughly related to a geographical embedding, making small degrees of separation surprising. (2) Often we are thinking of more properties than just small-world (low diameter). Social networks have lots of unusual properties that Erdos-Renyi graphs don't have. (Come to think of it, their diameter is more than $2$, and we just showed this is extremely unusual.)


