Problem 580

Let $G$ be a graph on $n$ vertices such that at least $n/2$ vertices have degree at least $n/2$ . Must $G$ contain every tree on at most $n/2$ vertices?

Source: erdosproblems.com/580

Graph theory

Wiki page

Status

Open

No claim settles this problem.

Decidable is the site's label; it describes the shape of what remains and is not a theorem, and the problem is open on the claims recorded here. Proved for all sufficiently large $n$ : Zhao's Theorem 1.6 [Zh11] (Electron. J. Combin. 18 (2011), P27, refereed; result page) gives a threshold $n_0$ such that for every $n\ge n_0$ a graph of order $n$ with at least $\lceil n/2\rceil$ vertices of degree at least $\lceil n/2\rceil$ contains every tree with at most $\lfloor n/2\rfloor$ edges, which answers the site's question affirmatively for $n\ge n_0$ ; it is recorded as an accepted partial claim, the reduction to a finite check, on its claim page (Zhao, 2011). The threshold is not made explicit (the proof uses the Regularity Lemma), so the finite remainder $n<n_0$ has no stated bound and no source on record settles it; the earlier approximate theorem of Ajtai, Komlós and Szemerédi [AKS95] (quoted through Zhao's Theorem 1.5 and Chung's Problem (69); the original is not held) has $(1+\rho)n/2$ in both places. The site's proof-claim tab carries one partial claim of a computer-assisted verification for $n\le19$ , unreviewed, recorded as a pending partial claim on its claim page (Zeraoulia, 2026). The site's label here stands for a statement proved for all $n\ge n_0$ with $n_0$ unknown and unchecked for finitely many $n$ ; this page keeps the label and records that reading without deciding whether the label's definition fits it.

Zh11: Zhao, Yi, Proof of the $(n/2-n/2-n/2)$ conjecture for large $n$ . Electron. J. Combin. 18 (2011), no. 1, Paper 27, 61 pp., doi:10.37236/514 (submitted 6 June 2008, accepted 22 January 2011, published 4 February 2011, by its Crossref record); Conjecture 1.3, Theorem 1.5 and Theorem 1.6, p. 2; Construction 1.7, p. 3. Library home: Zhao 2011 (the journal edition).
AKS95: Ajtai, Miklós and Komlós, János and Szemerédi, Endre, On a conjecture of Loebl. Graph theory, combinatorics, and algorithms, Vol. 1, 2 (Kalamazoo, MI, 1992) (1995), 1135--1146. Not held; its theorem is quoted here as Zhao's Theorem 1.5 (his [2]).
EFLS95: Erdős, P. and Füredi, Z. and Loebl, M. and Sós, V. T., Discrepancy of trees. Studia Sci. Math. Hungar. 30 (1995), no. 1--2, 47--57 (the site's reference text and Zhao's [8]). Not held (past the Rényi archive's 1989 cutoff); Zhao cites it for Loebl's conjecture and for the Komlós--Sós generalization.
ChGr98: Chung, F. and Graham, R., Erdős on graphs: his legacy of unsolved problems. A K Peters (1998); Zhao points to its p. 44 for the conjecture's name. Not held.
Ch97: Chung, F. R. K., Open problems of Paul Erdős in graph theory. J. Graph Theory 25 (1997), 3--36; Problem (69), p. 18 of the author preprint: the conjecture in the site's vertex form ("contains any tree on at most $n/2$ vertices"), attributed to Erdős, Füredi, Loebl and Sós (its [99], the paper [EFLS95]), with the Ajtai--Komlós--Szemerédi asymptotic version (its [4], the paper [AKS95]), also stated for trees on at most $n/2$ vertices, and the Komlós--Sós generalization for trees with $k$ vertices. Not cited by the site. Library home: Chung 1997 (the author preprint; Problem (69) is not paged on the card).

Problem 580

Status

Proof claims

Discussion