Using minimum degree to bound average distance

We show the average distance μ of a connected graph with n vertices, e edges and minimum degree d satisfiesμ⩽⌊(n+1)n(n−1)−2ed+1⌋n(n−1).This improves conjectures of the computer program Graffiti (Fajtlowicz, Written on the wall, Conjectures made by program Graffiti, University of Houston, 1990), and He and Li (Math. Appl. 4 (1991) 28–34) and the results of Kouider and Winkler (J. Graph Theory 25 (1997) 95–99). The bound is sharp since complete graphs yield equality.