  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.
