On the extrema of the mean subtree order of graphs

Abstract

It has been conjectured that the minimum and maximum of the mean subtree order among connected graphs of order $n$ are attained by the path $P_n$ and clique $K_n$, respectively. Extending ideas due to Haslegrave and Vince, we confirm that the minimum is indeed attained by $P_n$. We also show that the maximum is attained by $K_n$ by proving that the ratio between spanning and almost spanning trees is maximised by the clique and applying a double-counting argument.

18 pages, 3 figures (difference with v1: proof for maximum version added)