In the set of all connected, undirected and simple graphes where the numbers of vertices and edges are known, what are the shortest and longest average path length (as defined here: http://en.wikipedia.org/wiki/Average_path_length)?
In other words: if I were to write a code iterating through all possible connected, undirected and simple graphes of n vertices and m edges, and if, for each graph, I'd have the code compute the average path length and put this number in an array, what would be, at the end of the last iteration, the highest and lowest numbers of this array?
Best Answer
Here is a solution for the least possible average path length for a connected graph on $n$ vertices and $m$ edges:
Note that the least possible average path length would be achieved in a graph $G$ for which each pair of vertices connected by an edge in $G$ have distance 1, and all other pairs of vertices have distance 2. Then the average path length would be:
$$\frac{2}{n(n-1)} \left(m + 2\left(\binom{n}{2}-m\right)\right) = 2\left(1 - \frac{m}{n(n-1)}\right)$$
But this bound is achievable. In any graph $G$ with a vertex of degree $n-1$, each pair of vertices connected by an edge are at distance 1, while all other pairs of vertices are at distance 2.