# Graph containing all trees?

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

• Great question! I read it and thought, "This looks like something Bill would be interested in. Oh wait..." – Noah Stein Feb 3 '11 at 20:13

See Chung and Graham, On Universal Graphs for Spanning Trees. They prove that the number of edges is $\Theta(n\log n)$.

• Thanks! That's perfect. They also explictly construct such a graph in the paper. For the record, the reference is from J. London Math. Soc. (2), 27 (1983), pp 203-211. – Bill Bradley Feb 5 '11 at 17:41

Well, $O(n)$ will not do, as you need 1 vertex of degree $n-1$, a total of two vertices of degree $\ge \frac{n}{2}$, etc., to embedd all the trees with few vertices of high degree and only leaves otherwise. That should get you $cn\log n$ edges as a lower bound.

My guess is that this should be about right asymptotically, as you should be able to take a random graph with average degree $c\Delta\log n$ to get (all?) trees of max degree $\Delta$ (see http://arxiv.org/abs/1007.2326), and add some large degree vertices to get all other trees from this.

• Some care must be taken here: the star on $n-1$ vertices has maximum degree $n-1$. A tree given by an edge with each endpoint adjacent to $\frac{n-2}{2}$ vertices has two vertices of maximum degree $\frac{n-1}{2}$. For $k \geq 3$, the tree with a $k$-degree vertex whose neighbors are adjacent to $\frac{n-(k+1)}{k}$ other vertices has $k$ vertices of maximum degree $\frac{n-1}{k}$. Following your technique, the $k$ vertices of degree at least $\frac{n-1}{k}$ could be the first $k$ of the $k+1$ vertices of degree at least $\frac{n-1}{k+1}$, but one is missing. This gives $nH_n = cn\log n$ edges. – Derrick Stolee Feb 3 '11 at 19:43

The standard term is "universal graphs", I think. See http://en.wikipedia.org/wiki/Universal_graph According to that entry the answer is indeed $O(n \log n)$.

• Isn't the n log n bound there for bounded degree planar graphs ? For polytrees it seems a little less, however it might not be possible to capture any given tree as an induced subgraph of a polytree. – Suresh Venkat Feb 3 '11 at 15:36
• This answer is correct that the standard term is universal graphs, but the Wikipedia article doesn't seem to have the information about trees in it. Maybe someone should add it... – David Eppstein Feb 3 '11 at 23:19

it is useful.