Loebl's Conjecture

Loebl's conjecture asserts that a simple graph on vertices with at least vertices of vertex degree at least contains every tree with at most edges (Erdős et al. 1995, Zhao 2011). Zhao (2011) proved the assertion for sufficiently large .

The related formulation recorded as problem 580 asks for every tree with at most vertices, rather than edges. These formulations differ by one graph vertex; the published large-parameter theorem establishes the stronger edge-count version.

The vertex-count version is problem 580 in the Erdős problems collection (Bloom 2026).