Expected shortest path in random graph Consider all connected graphs with $n$ verticies where each vertex connects to $k$ other verticies. We choose such a graph at random. What is the expected value of the shortest path between two random points? What is the expected value of the maximal shortest path?
If an exact solution would be too complicated, I would also appreciate an approximate solution for $k<<n$.

This seems like a hard problem. For $k=2$ you can do exact calculations because the graph is a single cycle. For a random $k$-connected graph where $ k << n$ and $k > 2$, you can argue that for a given chosen starting vertex $v$, there will be expected $\Theta(k(k-1)^{m-1})$ vertices $w$ that will have a shortest path of length $m$ from $v$ to $w$ when $k$ and $m$ are small, so you should get something like $\log_{k-1} n$ or very close for the expected value of the shortest path length between two random points when $k << n$.  Arguing for the expected length of the maximal shortest path seems trickier, but I would be surprised if it wasn't also $O(\log_k n)$ for fixed $k > 2$ when $n$ is large.
