Today’s entry is a Theorem of the Day:

The Panarboreal Theorem:

Let $T_n$ denote the set of all unlabelled trees on n edges and denote by $s(T_n)$ the minimum number of edges which an (n+1)-vertex graph must have in order that it contains every tree in $T_n$ as a subgraph. Then $s(T_n)\sim cn\log n$ where c is a constant satisfying $\frac{1}{2}\le c\le \frac{5}{log4}$.

It’s thought that the upper bound on the value could be improved on – so there’s still work to be done on this problem. For more information, and some lovely diagrams of trees, see the full listing at Theorem of the Day: the Panarboreal Theorem.

This is part of the Aperiodical Advent Calendar. We’ll be posting a new surprise for you each morning until Christmas!