Zhuo Li

Subtree Counts and the Maximum Mean Subtree Order

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: $\mu(G)\leq\mu(K_n)$, wi...