Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

2 Answers 2

up vote 0 down vote accepted

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.

share|improve this answer

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

share|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.