{"id":"arxiv/2609.14355","url":"https://arxiv.org/abs/2609.14355","tags":["math.CO"],"score":0,"title":"Subtree Counts and the Maximum Mean Subtree Order","domain":"math.CO","source":"arxiv","authors":["Jungang Chen","Xian'an Jin","Zhuo Li","Hongxia Ma"],"reviews":0,"subject":"math.CO","summary":"For a finite simple graph $G$ of positive order, let $s_k(G)$ be the number of its $k$-vertex tree subgraphs. We prove that, among graphs of a fixed order $n$, the ratios $s_k(G)/s_k(K_n)$ form a nonincreasing sequence in $k$. It follows that the complete graph maximizes the mean subtree order: $μ(G)\\leqμ(K_n)$, with equality if and only if $G$ is complete. This monotonicity theorem also establishes the $s_{n-1}$-to-$s_n$ ratio conjecture posed in recent work on extremal mean subtree order. The proof lifts a known coupling of rooted Cayley-tree shapes of consecutive orders to uniform labeled…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-13","reactions":{}}