A note on universal graphs for spanning trees

Abstract

Chung and Graham considered the problem of minimizing the number of edges in an $n$-vertex graph containing all $n$-vertex trees as a subgraph. They showed that such a graph has at least $\frac{1}{2}n\log n$ edges. In this note, we improve this lower estimate to $n\log n$.

corrected typos