THEOREM OF THE DAY: The Panarboreal Formula

Theorem

Denote by s(n) the minimum number of edges a graph G on n vertices can have so that any tree on n vertices is isomorphic to some spanning tree of G. Then s(n) ∼ cn log n where c is a constant satisfying 1/2 ≤ c ≤ 5/ log 4.

Click on the image.