Counting trees in graphs (Q311564)

Summary: \textit{P. Erdős} and \textit{M. Simonovits} [Combinatorica 2, 275--288 (1982; Zbl 0508.05043)] proved that the number of paths of length \(t\) in an \(n\)-vertex graph of average degree \(d\) is at least \((1-\delta)nd(d-1) \cdots (d-t+1)\), where \(\delta = (\log d)^{-1/2 + o(1)}\) as \(d \to \infty\). In this paper, we strengthen and generalize this result as follows. Let \(T\) be a tree with \(t\) edges. We prove that for any \(n\)-vertex graph \(G\) of average degree \(d\) and minimum degree greater than \(t\), the number of labelled copies of \(T\) in \(G\) is at least \[ (1-\varepsilon)nd(d-1)\cdots(d-t+1) \] where \(\varepsilon = O(d^{-2})\) as \(d \to \infty\). This bound is tight except for the term \(1 - \varepsilon\), as shown by a disjoint union of cliques. Our proof is obtained by first showing a lower bound that is a convex function of the degree sequence of \(G\), and this answers a question of \textit{D. Dellamonica} et. al. [J. Comb. 3, No. 1, 49--62 (2012; Zbl 1272.05084)].