Problem dossier · Graph Decompositions
Erdős–Sós conjecture
Every graph with average degree greater than k − 1 contains every tree with k edges as a subgraph.
§1
Status
Open in general; an announced proof for large k (Ajtai–Komlós–Simonovits–Szemerédi) remains unpublished. Known for paths (Erdős–Gallai), spiders, and many tree classes.
Think you can crack this one? Read the playbook before you announce →
§2
The Angle of Attack
Test the bound on random and extremal graphs against hard tree shapes (brooms, caterpillars); search for near-tight configurations in small k.
Tags: trees · subgraphs · average degree · extremal
§3
The Lab
No instruments built yet. When this problem gets tackled, its interactive instruments — explorers, searches, verifiers running in the browser — live here. See the Collatz dossier for what a fully tackled problem looks like.
§4
The Log
Empty. Work on this problem gets logged here as dated entries — constructions tried, code run, dead ends included. Dead ends are results.
§5
Related Problems
More open problems in Graph Decompositions and adjacent territory.
- 1-Factorization conjecture — Graph Decompositions
- Gallai's path decomposition conjecture — Graph Decompositions
- Linear arboricity conjecture — Graph Decompositions
- Overfull conjecture — Graph Decompositions
- Frankl's union-closed sets conjecture — Graph Theory
- No-three-in-line problem — Graph Theory