Average distance in graphs and eigenvalues

Brendan McKay gave the following formula relating the average distance between pairs of vertices in a tree TT and the eigenvalues of its Laplacian: d¯T=2n−1∑i=2n1λi. By modifying Mohar’s proof of this result, we prove that for any graph GG, its average distance, d¯G, between pairs of vertices satisfies the following inequality: d¯G≥2n−1∑i=2n1λi. This solves a conjecture of Graffiti  . We also present a generalization of this result to the average of suitably defined distances for kk subsets of a graph.