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.)



Graph containing all trees?
See Chung and Graham, [On Universal Graphs for Spanning Trees](http://www.math.ucsd.edu/~ronspubs/83_06_universal_trees.pdf). They prove that the number of edges is $\Theta(n\log n)$.


