On Universal Graphs for Trees and Tree-Like Graphs

Abstract

Chung and Graham [J. London Math. Soc. 1983] claimed to prove that there exists an $n$-vertex graph $G$ with $\frac{5}{2}n{\log }_{2}n+O(n)$ edges that contains every $n$-vertex tree as a subgraph. Frati, Hoffmann and Tóth [Combin. Probab. Comput. 2023] discovered an error in the proof. By adding more edges to $G$ the error can be corrected, bringing the number of edges in $G$ to $\frac{7}{2}n{\log }_{2}n+O(n).$ We make the first improvement to Chung and Graham's bound in over four decades by showing that there exists an $n$-vertex graph with $\frac{14}{5}n{\log }_{2}n+O(n)$ edges that contains every $n$-vertex tree as a subgraph. Furthermore, we generalise this bound for treewidth-$k$ graphs by showing that there exists a graph with $O(kn\log (n/k+1))$ edges that contains every $n$-vertex treewidth-$k$ graph as a subgraph. This is best possible in the sense that $\hat{I}\text{c◯}(kn\log (n/k+1))$ edges are required.

v4: minor technical revisions, slight improvement to treewidth bound