TREE-MINIMAL GRAPHS ARE ALMOST REGULAR

Abstract. For all fixed trees T and any graph G we derive a counting formula for the number N̂T (G) of homomorphisms from T to G in terms of the degree sequence of G. As a consequence we obtain that any n-vertex graph G with edge density p = p(n) n−1/(t−2), which contains at most (1 + o(1))pt−1nt copies of some fixed tree T with t ≥ 3 vertices must be almost regular, i.e., v∈V (G) |deg(v) − pn | = o(pn2)