# Graph containing every trees of size $n$ as subgraphs

What is the minimum number of edges of graph $G$, so that every tree of size $n$ is a subgraph of $G$?

I personally managed to find a lower bound of $c n \log n$ and an upper bound of $C n \log ^2 n$. But what I'm actually trying to ask is not the problem itself, but reference for it. I strongly believe that this problem would had been considered by some mathematicians, but searching gives articles about minimum spanning tree. Where can I find some results for this problem?

-

## 2 Answers

Such kind of graphs are called universal graphs, and Chung and Graham proved that there exists such a graph with $O(n \log n)$ edges.

-

This is called the Erdős and Sós conjecture on trees. See here. The conjecture was recently proved.

-
Do you, by any chance, have a reference to the proof of the conjecture ? – Manuel Lafond Jul 23 '14 at 1:59
Thanks for this interesting conjecture. But what I'm asking is the minimum number of edges required for some graph, while the conjecture is asking for all graph. – Jineon Baek Jul 23 '14 at 7:18
@manuellafond It was presented by Szemerédi at the Erdos conference last year. – Jernej Jul 23 '14 at 19:36