The number of trees in a graph

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.

No reviews yet.

No comments yet.