Number of edges to force all trees
- All (170)
- Ramsey Theory (40)
- Extremal Graph Theory (40)
- Coloring, Packing, and Covering (25)
- Random Graphs and Graph Enumeration (16)
- Hypergraphs (35)
- Infinite Graphs (14)
About This Site
One of the most tantalizing problems in extremal graph theory is the following classic problem:
A conjecture on trees (proposed by Erdös and Sós, 1962)Every graph on \(n\) vertices having at least \(n(k-1)/2+1\) edges must contain as a subgraph every tree of \(k+1\) vertices, for \(n \geq k+1\).
This conjecture, if true, would be best possible. It can be easily proved by induction that every graph on \( n\) vertices having at least \( n(k-1)+1\) edges must contain every tree of \( k+1\) vertices.
Some asymptotic results for this conjecture have been given by Komlós and Szemerédi (unpublished). Also, this conjecture has been proved for some special families of trees such as caterpillars. Brandt and Dobson  have proved the conjecture for graphs with girth at least \( 5\).
S. Brandt and E. Dobson, The Erdös-Sós conjecture for graphs
of girth \( 5\), Selected papers in honour of Paul Erdös on the
occasion of his 80th birthday (Keszthely, 1993), Discrete
Math. 150 (1996), 411-414.