Using minimum degree to bound average distance (Q1841923)

The authors show that the average distance \(\mu\) of a connected graph with \(n\) vertices, \(e\) edges and minimum degree \(d\) satisfies \[ \mu n(n-1)\leq \left\lfloor \frac{(n+1)n(n-1)-2e}{d+1} \right\rfloor . \] This improves conjectures of the computer program Graffiti, and \textit{W. He} and \textit{S. Li} [Math. Appl. 4, No. 2, 28-34 (1991; Zbl 0891.05030)] and the results of \textit{M. Kouider} and \textit{P. Winkler} [J. Graph Theory 25, No. 1, 95-99 (1997; Zbl 0872.05011)]. The bound is attained by complete graphs.