Average distance in graphs and eigenvalues

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