The \( (n/2-n/2-n/2) \) conjecture

The (\(n/2\)-\(n/2\)-\(n/2\)) conjecture (proposed by Erdös, Füredi, Loebl and Sós [2])

Let \(G\) be a graph with \(n\) vertices and suppose at least \(n/2\) vertices have degree at least \(n/2\). Then \(G\) contains any tree on at most \(n/2\) vertices.

Ajtai, Komlós and Szemerédi [1] proved the following asymptotic version: If \( G\) has \( n\) vertices and at least \( (1+ \epsilon) n/2\) vertices have degree at least \( (1+ \epsilon) n/2\), then \( G\) contains any tree on at most \( n/2\) vertices if \( n\) is large enough (depending on \( \epsilon\)).

Komlós and Sós[2] conjectured the following generalization:

Let \( G\) be a graph with \( n\) vertices and suppose at least \( n/2\) vertices have degree at least \( k\). Then \( G\) contains any tree with \( k\) vertices.

Bibliography
1 M. Ajtai, J. Komlós and E. Szemerédi, On a conjecture of Loebl, Proc. of the 7th International Conference on Graph Theory, Combinatorics, and Algorithms, (Kalamazoo, Michigan, 1992), 1135-1146, Wiley, New York, 1995.

2 P. Erdös, Z. Füredi, M. Loebl and V. T. Sós, Discrepancy of trees, Combinatorics and its Applications to Regularity and Irregularity of Structures, (W. A. Deuber and V. T. Sós, eds), Studia Sci. Math. Hungar. 30 (1995), 47-57.