I am looking for information on the lower bound of the average shortest path in a connected undirected graph, given the number $n$ of vertices and number $k$ of edges in the graph.
I would like to know how this relates to the average shortest path in random graphs with the same $n$ and $k$.
"Practical" results based on approximations and heuristics are also useful.
The average shortest path is defined as $$ L = \frac{1}{n(n-1)}\sum_{i < j} s_{ij}, $$ where $s_{ij}$ is the smallest number of edges we need to traverse to move from vertex $i$ to vertex $j$ in the graph. I.e., take the length of the shortest path between all vertex pairs and average them.