Number of edges to force all trees

Home
Search
Subjects

About Erdös
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 [1] have proved the conjecture for graphs with girth at least $5$ .

Bibliography
1	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.