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$.
For fixed $k$, in "The Diameter of Random Regular Graphs", Bollobas and de la Vega proved that w.h.p. the diameter of the random $k$-regular graph is $\sim \log_{k-1}n$ (in fact, they show a much sharper concentration than this). Furthermore, one can also show that w.h.p. the distance between any two specific vertices in a $k-$regular graph chosen uniformly at random is also $\sim \log_{k-1}n$.
By and large, when one runs a breadth-first search in this model, each new level is roughly $k-1$ times the previous, and the vast majority of the vertices are reached in the last few steps.
I imagine if $k$ is allowed to vary with $n$ and not be too large, you would find similar behavior; however, I don't know where the threshold for too large would be.
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.
