Let $G$ be a directed graph that has $n$ nodes and is strongly connected. Define a random path as the following: Pick two vertices uniformly at random and find the shortest path going from one vertex to another (either way is fine). Can we bound the length of a random path of $G$ if we know the size of $|E|$?
For example, if $E = O(n)$, then it seems easy to construct a graph with only large paths. However, if $E = \Theta(n^2)$, then it is likely that the graph has short expected path size. What if $|E| = o(n^2)$ or $O(n \log n)$ ? Can we derive any bounds for the expected length of a random path in these cases? What if our graph is undirected?