The number of trees in a graph

Dhruv Mubayi, Jacques Verstraete

Published 2015-11-23Version 1

Let $T$ be a tree with $t$ edges. We show that the number of isomorphic (labeled) copies of $T$ in a graph $G = (V,E)$ of minimum degree at least $t$ is at least \[2|E| \prod_{v \in V} (d(v) - t + 1)^{\frac{(t-1)d(v)}{2|E|}}.\] Consequently, any $n$-vertex graph of average degree $d$ and minimum degree at least $t$ contains at least $$nd(d-t+1)^{t-1}$$ isomorphic (labeled) copies of $T$. This answers a question of Dellamonica et. al. (where the above statement was proved when $T$ is the path with three edges) while extending an old result of Erd\H os and Simonovits.