Consider graphs on $n$ nodes. I am trying to find a graph $G$ that contains all $n$-node trees as sub-graphs but contains as few edges as possible. The complete graph $K_n$ suffices, but can we get by with fewer edges? Maybe $O(n)$ edges?
(This problem arose in the context of circuit design, where edges in $G$ correspond to wires in a chip layout.)