Optimal Bounds on Spanning Tree Embeddings

Csongor Beke, Vladimir Bošković, Nina Kamčev +1

We prove that the number of labelled embeddings of any $n$-vertex tree $T$ into an $n$-vertex graph $G$ of maximum degree $d$ satisfies $$ \mathrm{inj}(T,G) \leq (d/e)^n \exp(o_d(1…