\documentclass[10pt]{article}
\usepackage[margin=0.75in]{geometry}
\usepackage{amsmath,amssymb,amsthm}
\usepackage[hidelinks]{hyperref}
\usepackage[small,compact]{titlesec}
\emergencystretch=1em
\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}

\title{Contracting a pendant edge can increase the mean subtree order}
\author{Alexander M. Kramer\thanks{Independent Researcher. \texttt{akramer.alex@gmail.com}. The construction, proof and text were developed with large language models (Anthropic Claude and OpenAI Codex) under the author's direction, and the author checked and revised the argument and text.}}
\date{\today}

\begin{document}
\maketitle

\begin{abstract}
Cambie, Jooken and Wagner conjectured that contracting an edge of a connected graph decreases the mean subtree order by at least $1/3$, as it does for trees. We construct unicyclic graphs of order $n$ and maximum degree $3$ in which contracting a pendant edge increases the mean subtree order by $n/450+O(1)$, disproving the conjecture. In this family the bound first fails at $481$ vertices and contraction first increases the mean at $631$ vertices.
\end{abstract}

\section{Introduction}

Throughout this paper, we consider finite, simple and connected graphs. A subtree of a graph $G$ is a subgraph of $G$ that is a tree, not necessarily induced (single vertices included). Let $N(G)$ be the number of subtrees of $G$ and $R(G)$ the total order of all subtrees of $G$, that is, the sum of their orders (numbers of vertices). The mean subtree order of $G$ is $\mu(G)=R(G)/N(G)$, and the local mean $\mu(G,v)$ at a vertex $v$ is the average order of the subtrees containing $v$. For an edge $e$, $G/e$ denotes the graph obtained from $G$ by contracting $e$.

The mean subtree order of trees was introduced by Jamison \cite{J83}, who later conjectured \cite[Conj.~5.6]{J84} that $\mu(T)-\mu(T/e)\geq1/3$ for every edge $e$ of every tree $T$. Luo, Xu, Wagner and Wang \cite{LXWW23} proved this for pendant edges and Wang \cite{W24} in general. Cambie, Jooken and Wagner \cite[Conj.~1.8]{CJW} conjectured that $\mu(G)-\mu(G/e)\geq1/3$ for every edge $e$ of every connected graph $G$, with equality if and only if $G$ is a path. We show that the conjecture fails even for pendant edges of unicyclic graphs with maximum degree $3$.

For an integer $t\geq1$, let $H_t$ be the graph obtained from the cycle labelled $0,1,\ldots,8t-1$ in cyclic order by joining one end of a path on $t$ new vertices to vertex $0$, and one end of another such path to vertex $2t$. We call $0$ and $2t$ the attachment vertices and the two paths the attached paths. Let $v$ be the vertex $t$, and let $G_t$ be obtained from $H_t$ by adding a new vertex $w$ adjacent to $v$. Both graphs are unicyclic with maximum degree $3$, $G_t$ has order $n=10t+1$, and $G_t/vw=H_t$ because $w$ is a leaf.

\begin{theorem}\label{thm:main}
As $t\to\infty$,
\[
\mu(G_t)-\mu(G_t/vw)=-\frac{t}{45}+O(1)=-\frac{n}{450}+O(1).
\]
The smallest $t$ with $\mu(G_t)-\mu(G_t/vw)<1/3$ is $t=48$, and the smallest $t$ with $\mu(G_t)<\mu(G_t/vw)$ is $t=63$, where $n=631$ and
\[
\mu(G_{63})-\mu(G_{63}/vw)=-\frac{4293783638}{49101085318287}.
\]
\end{theorem}

The graph $H_t$ is a variant of the graph $DB^{\star1}_{n,w}$ in the proof of \cite[Prop.~5.1]{CJW}, with the attachment vertices at distance $2t$ instead of $2$ and paths in place of sets of leaves. For sufficiently large $t$, the local mean $\mu(H_t,v)$ lies below $\mu(H_t)$ by an amount linear in $t$, which cannot happen in a tree \cite{J83}. Adding $w$ then lowers the mean, so contracting $vw$ raises it.

\section{Proof of Theorem~\ref{thm:main}}

\begin{lemma}\label{lem:gaps}
Let $M$ be a set of $j\geq1$ vertices of the cycle $C_m$, and let $d_1,\ldots,d_j$ be the numbers of edges on the arcs of $C_m$ between consecutive vertices of $M$ (so $d_1=m$ if $j=1$). The subtrees of $C_m$ are its paths, the $m$ spanning paths being distinct. The number $Q$ and the total order $S$ of the subtrees of $C_m$ containing $M$ are
\[
Q=m+\sum_{i=1}^{j}\binom{d_i}{2},\qquad S=mQ-\sum_{i=1}^{j}\binom{d_i+1}{3}.
\]
For $M=\emptyset$, $Q=m^2$ and $S=m^2(m+1)/2$.
\end{lemma}

\begin{proof}
A subtree of $C_m$ containing $M$ is one of the $m$ spanning paths, or it omits a nonempty interval of vertices not in $M$, which lies inside one arc. An arc of length $d_i$ has $d_i-1$ interior vertices, hence $\binom{d_i}{2}$ such intervals, and their numbers of vertices sum to $\sum_{\ell=1}^{d_i-1}\ell(d_i-\ell)=\binom{d_i+1}{3}$. For $M=\emptyset$ there are $m$ paths of each order $\ell<m$ and $m$ spanning paths.
\end{proof}

\begin{proof}[Proof of Theorem~\ref{thm:main}]
Let $N_t=N(H_t)$ and $R_t=R(H_t)$, and let $A_t$ be the number and $B_t$ the total order of the subtrees of $H_t$ containing $v$. The subtrees of $G_t$ are the subtrees of $H_t$, the single vertex $w$, and the subtrees of $H_t$ containing $v$ extended by the edge $vw$. Hence
\begin{equation}\label{eq:leaf}
N(G_t)=N_t+A_t+1,\qquad R(G_t)=R_t+B_t+A_t+1.
\end{equation}

A subtree of $H_t$ meeting the cycle intersects it in a path, since the attached paths cannot connect distinct cycle vertices. We call it the cycle path of the subtree. The subtree is determined by its cycle path together with an initial segment, possibly empty, of the attached path at each attachment vertex on the cycle path. There are $t+1$ choices for each segment, with $t/2$ vertices on average, so a cycle path through $h$ attachment vertices yields $(t+1)^h$ subtrees, with $ht/2$ added vertices on average.

For a set $X$ of cycle vertices, let $Q_X$ and $S_X$ be the number and total order of cycle paths containing $X$. Let $U=\{0,2t\}$. For a cycle path $P$ through $h$ attachment vertices, expand $(t+1)^h=\sum_{X\subseteq U\cap V(P)}t^{|X|}$. Summing over $P$ gives
\begin{align}
N_t&=\sum_{X\subseteq U}t^{|X|}Q_X+t(t+1),\label{eq:sum}\\
R_t&=\sum_{X\subseteq U}t^{|X|}
 \Bigl(S_X+\tfrac12(t+1)|X|Q_X\Bigr)+\tfrac13t(t+1)(t+2).\notag
\end{align}
The last terms account for the subtrees contained in the attached paths, and the second term in $R_t$ is justified by the identity
\[
\sum_{X\subseteq U\cap V(P)}|X|t^{|X|}
=ht(t+1)^{h-1}.
\]
Replacing $Q_X,S_X$ by $Q_{X\cup\{v\}},S_{X\cup\{v\}}$ and omitting the last terms gives $A_t,B_t$.

Lemma~\ref{lem:gaps} with $m=8t$ gives the following values.
{\small
\[
\begin{array}{l|l|r|r}
X & \text{arc lengths} & Q_X & 3S_X\\ \hline
\emptyset & \text{none} & 64t^2 & 768t^3+96t^2\\
\{0\},\{2t\},\{v\} & (8t) & 32t^2+4t & 512t^3+96t^2+4t\\
\{0,2t\} & (2t,6t) & 20t^2+4t & 368t^3+96t^2+4t\\
\{0,v\},\{2t,v\} & (t,7t) & 25t^2+4t & 428t^3+96t^2+4t\\
\{0,2t,v\} & (t,t,6t) & 19t^2+4t & 347t^3+96t^2+4t
\end{array}
\]
}
Substituting into \eqref{eq:sum}, for instance $N_t=Q_\emptyset+2tQ_{\{0\}}+t^2Q_{\{0,2t\}}+t(t+1)$, and expanding,
\begin{align*}
N_t&=20t^4+68t^3+73t^2+t,&
3R_t&=428t^5+1288t^4+1085t^3+119t^2+2t,\\
A_t&=19t^4+54t^3+40t^2+4t,&
3B_t&=404t^5+1096t^4+807t^3+116t^2+4t.
\end{align*}
These values were also verified by computer for $t\leq6$, by enumerating the connected vertex sets of $H_t$ and $G_t$ and counting the spanning trees of each induced subgraph.

These polynomials and \eqref{eq:leaf} give $\mu(H_t)=\frac{107}{15}t+O(1)$ and $\mu(G_t)=\frac{64}{9}t+O(1)$. Their difference is $-t/45+O(1)=-n/450+O(1)$. They also give $\mu(H_t,v)-\mu(H_t)=B_t/A_t-R_t/N_t=-13t/285+O(1)$, as claimed above.

Evaluating the polynomials for $1\leq t\leq63$ shows that $\mu(G_t)-\mu(H_t)\geq1/3$ for $t\leq47$, $\mu(G_{48})-\mu(H_{48})<1/3$, and $\mu(G_t)>\mu(H_t)$ for $t\leq62$. At $t=63$ the polynomials give $N(H_{63})=332352216$, $R(H_{63})=148441475868$, $N(G_{63})=645320026$ and $R(G_{63})=288225062749$, and the difference of means is the fraction in Theorem~\ref{thm:main}.
\end{proof}

\begin{thebibliography}{9}\small\setlength{\itemsep}{0pt}
\bibitem{CJW}
S.~Cambie, J.~Jooken and S.~Wagner, On the extrema of the mean subtree order of graphs, arXiv:2508.20593 (2025), version 2 (2026).
\bibitem{J83}
R.~E.~Jamison, On the average number of nodes in a subtree of a tree,
J. Combin. Theory Ser. B 35 (1983), 207--223.
\bibitem{J84}
R.~E.~Jamison, Monotonicity of the mean order of subtrees,
J. Combin. Theory Ser. B 37 (1984), 70--78.
\bibitem{LXWW23}
Z.~Luo, K.~Xu, S.~Wagner and H.~Wang, On the mean subtree order of trees under edge contraction,
J. Graph Theory 102 (2023), 535--551.
\bibitem{W24}
R.~Wang, On the difference of mean subtree orders under edge contraction,
J. Combin. Theory Ser. B 169 (2024), 45--62.
\end{thebibliography}

\end{document}