On the mean subtree order of graphs under edge addition

For a graph G , the mean subtree order of G is the average order of a subtree of G . In this note, we provide counterexamples to a recent conjecture of Chin, Gordon, MacPhee, and Vincent, that for every connected graph G and every pair of distinct vertices u and v of G , the addition of the edge between u and v increases the mean subtree order. In fact, we show that the addition of a single edge between a pair of nonadjacent vertices in a graph of order n can decrease the mean subtree order by as much as n ∕ 3 asymptotically. We propose the weaker conjecture that for every connected graph G which is not complete, there exists a pair of nonadjacent vertices u and v , such that the addition of the edge between u and v increases the mean subtree order. We prove this conjecture in the special case that G is a tree.