Erdős #548 — Erdős–Sós conjecture: $\\frac{k-1}{2}n+1$ edges force every $(k+1)$-tree

Statement

Let $n\geq k+1$. Every graph on $n$ vertices with at least $\frac{k-1}{2}n+1$ edges contains every tree on $k+1$ vertices (i.e. every tree with $k$ edges). (erdosproblems.com/548, direct fetch.) This is the Erdős–Sós conjecture, one of the best-known open problems in extremal graph theory.

Facts

- Prize \$100; status marked FALSIFIABLE — "Open, but could be disproved with a finite counterexample" (erdosproblems.com/548, last edited 07 March 2026). A single $n$-vertex graph with $\geq \frac{k-1}{2}n+1$ edges avoiding some fixed $(k+1)$-vertex tree would refute it. - Falsifiable: yes, in principle — but $k$ is a free parameter, so "finite counterexample" really means "for some fixed $k$, a finite search over $n$-vertex graphs and $(k+1)$-vertex trees"; there is no a priori bound making the full conjecture (all $k$) checkable by one finite computation. - Origin: posed by Erdős (and Sós) — refs [Er64c] (Theory of Graphs and its Applications, Smolenice 1963, MR180500), [Er74c] (Extremal problems on graphs and hypergraphs, 1974, MR360350), [Er78] (Proc. 9th Southeastern Conf., 1978, MR527930), [Er93] (Quaestiones Math., 1993, MR1254162), [Va99] (Budapest 1999 booklet §3.55) — all bib entries fetched directly from erdosproblems.com/bibs/. - Erdős and Sós also conjectured the stronger forest version: every graph with at least $\max\big(\binom{2k-1}{2}+1,\ (k-1)n-(k-1)^2+\binom{k-1}{2}+1\big)$ edges contains every forest with $k$ edges (erdosproblems.com/548). Erdős–Gallai [ErGa59] proved the analogous threshold forcing $k$ independent edges (a matching), which is the base case Erdős and Sós built on. - Known results / best bounds (from erdosproblems.com/548 remarks, cross-checked): - Trivial for stars [Er78]. Proved for paths by Erdős and Gallai (cited in [Er78]). - Elementary induction gives every tree on $k+1$ vertices is forced by $n(k-1)+1$ edges (a factor-2-off bound compared to the conjectured $\tfrac{k-1}{2}n+1$). - Proved for graphs of girth $\geq 5$: Brandt & Dobson [BrDo96], Discrete Math. 1996 (MR1392751). - Proved for graphs whose complement has girth $\geq 5$: Wang, Li, Liu [WLL00], Ars Combin. 2000 (MR1755223). - Proved for graphs containing no $C_4$: Saclé & Woźniak [SaWo97], JCTB 1997 (MR1459879). - Proved for graphs whose complement contains no $C_4$: Yin & Li [YiLi04], Acta Math. Appl. Sin. 2004 (MR2086761). - Proved for trees of diameter $\leq 4$: A. McLennan, "The Erdős–Sós conjecture for trees of diameter four," J. Graph Theory 49 (2005) (cross-checked via web search, ResearchGate/Wiley listing). - Proved for trees with a vertex adjacent to $\geq (\ell-1)/2$ leaves ($\ell=$ tree order): A. Sidorenko (cross-checked via web search summaries of the survey literature). - Proved for caterpillars: M. Perles (geometric argument; cross-checked via secondary citations in the spiders/caterpillars literature, not independently read in primary form — flagged as needing a primary-source check). - Proved for all spiders (trees with $\leq 1$ vertex of degree $>2$): Fan, Hong, Liu, "The Erdős–Sós Conjecture for Spiders," arXiv:1804.06567 (2018). - Unpublished announced full proof for large $k$: Ajtai, Komlós, Simonovits, Szemerédi announced (late 1980s/1990s, e.g. cited as "in preparation") a proof of the conjecture for all sufficiently large $k$, using the regularity method — but it has never been published, and only some of the ideas have circulated (repeatedly noted as the central open gap in every later paper, e.g. arXiv:1906.10219, arXiv:2409.15191). - Rigorously published partial resolution of the AKSS claim (2020, bounded degree): Besomi, Pavez-Signé, Stein, "On the Erdős-Sós conjecture for trees with bounded degree," arXiv:1906.10219 / Combin. Probab. Comput. — prove the conjecture for trees of bounded maximum degree and large dense host graphs, via the regularity/absorption method; also derive multicolour Ramsey number bounds for such trees. Rozhoň, arXiv:1804.06791, independently gets an approximate version when the tree is linear-size in the host graph with sublinear max degree. - Sparse case closed for bounded-degree trees (2024): Alexey Pokrovskiy, "Hyperstability in the Erdős-Sós Conjecture," arXiv:2409.15191 — proves a rough structure theorem for $T$-free graphs ($T$ a bounded-degree tree): one can delete $o(|G||T|)$ edges to leave a subgraph whose components have covers of order $3|T|$, converting sparse-$T$-free questions into dense ones. Direct application stated in the abstract: "a proof of the Erdős-Sós Conjecture for large, bounded degree trees" — i.e. the conjecture is now a fully proved theorem in the bounded-max-degree, large-$k$ regime (no density restriction on the host graph needed). - Unbounded-degree trees, dense host graphs (2026, very recent): Davoodi, Piguet, Řada, Sanhueza-Matamala, "The asymptotic version of the Erdős-Sós conjecture and beyond," arXiv:2603.17755 (104pp) — prove an asymptotic version of a strengthening conjectured by Klimošová, Piguet, Rozhoň (minimum degree $k/2$ + enough vertices of degree $k$ forces every $k$-edge tree), and derive as a corollary "an asymptotic version of the Erdős–Sós conjecture for dense host graphs, which works without any bounded-degree restriction on the guest trees" — the first asymptotic confirmation removing the tree-degree restriction. They further combine with Pokrovskiy's structure theorem to transfer to sparse host graphs when the guest tree has bounded degree. - Remaining gap: the exact (non-asymptotic) conjecture for large $k$ with unbounded-degree trees is still not published/settled — this is precisely the content of the AKSS unpublished 1990s claim, still open in the literature as of this July 2026 search. - Related problems: erdos/547 — $R(T)\leq 2n-2$ for any $n$-vertex tree $T$ (DECIDABLE/resolved-up-to-finite-check on erdosproblems.com), directly implied by #548's conjectured bound (erdosproblems.com/547: "follows directly from the conjecture... and is therefore proved for all large $n$ assuming the announced [AKSS] proof... although this proof has not been published"; Zhao [Zh11] proved $R(T)\le 2n-2$ for all large $n$ by an independent method, sidestepping the gap). erdos/557 — multicolour analogue $R_k(T)\leq kn+O(1)$ for trees, explicitly "implied by [548]" (erdosproblems.com/557).

Literature state

Not resolved as stated (all $k$, exact threshold) — but substantially resolved in the literature for large $k$ under a bounded-degree restriction, and asymptotically resolved for dense host graphs with no degree restriction, as of 2024–2026. This is one of the most famous conjectures in extremal graph theory (posed by Erdős and Sós, restated by Erdős at least 4 times over 1964–1999). Confirmed still formally open by erdosproblems.com/548 (last edited 07 March 2026, 0 solutions claimed) and by github.com/teorth/erdosproblems data/problems.yaml (status.state: "falsifiable", last_update: 2025-08-31, formalized.state: "no").

Key facts from this search, in order of importance: 1. The historically load-bearing claim — AKSS unpublished proof for large $k$ — is still unpublished as of July 2026. Every recent paper (arXiv:1906.10219, arXiv:2409.15191, arXiv:2603.17755) still cites it as "announced but not published," and each frames itself as trying to independently establish (a special case of) the AKSS result rigorously. 2. Pokrovskiy 2024 (arXiv:2409.15191) is the strongest published result: a genuine, published proof of Erdős–Sós for large, bounded-maximum-degree trees, valid for sparse as well as dense host graphs (via his "hyperstability" structure theorem reducing sparse-$T$-free to dense-$T$-free). This is effectively the bounded-degree special case of AKSS, finally nailed down rigorously and published. 3. Davoodi–Piguet–Řada–Sanhueza-Matamala 2026 (arXiv:2603.17755) removes the bounded-degree restriction on the tree, but only asymptotically and only for dense host graphs (i.e. proves $\mathrm{ex}(n,T) \le (1+o(1))\frac{k-1}{2}n$ rather than the exact $\frac{k-1}{2}n+1$). They build on a conjectured strengthening by Klimošová, Piguet, Rozhoň and combine with Pokrovskiy's structure theorem to push part of the result to sparse host graphs (still requiring bounded tree degree there). 4. No AI-assisted or automated progress found: #548 does not appear anywhere in github.com/teorth/erdosproblems/wiki/AI-contributions-to-Erdős-problems (checked directly, full 678-line page, no match for "548" or "Sós"/"Sos"). 5. No formalization exists: data/problems.yaml confirms formalized.state: "no" — unlike some neighboring Erdős problems, #548 has not been stated in Lean. 6. Special-case landscape is dense and well-mapped: girth $\geq5$ graphs (Brandt–Dobson [BrDo96]), $C_4$-free graphs (Saclé–Woźniak [SaWo97]) and their complement analogues (Wang–Li–Liu [WLL00], Yin–Li [YiLi04]), diameter-$\leq4$ trees (McLennan 2005), high-leaf-degree trees (Sidorenko), caterpillars (Perles), and — the most recent structural class fully closed — all spiders (Fan–Hong–Liu, arXiv:1804.06567, 2018). The remaining open frontier for the *exact* conjecture is trees that are neither bounded-degree-and-large nor in one of these named structural families, and/or the small/medium-$k$ exact regime not covered by any asymptotic result.

Attack surface

- Mode: literature-resolution (primary) + derivation (secondary, only for very restricted new tree families or small-$k$ finite verification). - Concrete first experiment: NOT a good target for direct SAT/CP-SAT search on the general conjecture — $k$ is unbounded and the strongest open content (unbounded-degree trees, exact constant, all $k$) is a regularity-method / absorption-method proof problem, not a finite search. A genuinely useful, runnable first step instead: (1) enumerate all trees on $k+1\leq 12$ vertices and all graphs on $n\leq 20$–$24$ vertices with $\geq\frac{k-1}{2}n+1$ edges (via nauty/geng + a subgraph-isomorphism check, e.g. networkx VF2 or igraph) to brute-force-confirm the conjecture in the small-$k$/small-$n$ regime and hunt for near-tight extremal examples — this cannot refute the conjecture in general but (a) is a real falsification attempt at accessible scale and (b) surfaces extremal graphs that might suggest which non-bounded-degree tree families are hardest, informing which case to attack analytically next. (2) Read Pokrovskiy's arXiv:2409.15191 hyperstability structure theorem and the Davoodi–Piguet–Řada–Sanhueza-Matamala arXiv:2603.17755 Klimošová–Piguet–Rozhoň-conjecture proof in full, and check precisely which unbounded-degree tree families are NOT yet covered by combining the two — that gap is the actual open mathematical target now, not the whole conjecture. - Oracle: (a) for small finite instances, subgraph-isomorphism / tree-embedding is mechanically checkable (VF2, or ILP/SAT embedding-existence formulation) — a genuine finite counterexample at small $k,n$ would be a full falsification; (b) for the general/asymptotic literature-resolution question, "oracle" = re-deriving the exact reduction chain in arXiv:2409.15191 + arXiv:2603.17755 to confirm no silent gap remains for a specific bounded-degree-large-$k$ instance (checkable by careful reading, not computation). - Feasibility: LOW for a full, exact, all-$k$, unbounded-degree resolution — this is exactly the famous unpublished AKSS gap that professional extremal graph theorists (Rozhoň, Besomi–Pavez-Signé–Stein, Pokrovskiy, Davoodi–Piguet–Řada–Sanhueza-Matamala) have been chipping at for 15+ years with the regularity/absorption toolkit, most recently as of March 2026. MEDIUM feasibility for a genuine derivation contribution in a narrow lane: (i) small-$k$/small-$n$ exhaustive verification-and-extremal-example-mining is fully in reach computationally and could produce useful data even though it can't resolve the conjecture; (ii) carefully reading the two 2024/2026 papers to pin down the *exact* remaining open tree-family gap (unbounded-degree + sparse host, or unbounded-degree + exact-not-asymptotic even in dense host) is a well-defined, currently-active research question, not the whole 60-year-old conjecture.

Related

- erdos/547 — tree Ramsey number $R(T)\leq 2n-2$; directly implied by #548's conjectured bound (still open pending the same AKSS gap), though independently proved for large $n$ by Zhao [Zh11] via a different method (erdosproblems.com/547). - erdos/557 — multicolour tree Ramsey number $R_k(T)\leq kn+O(1)$; explicitly "implied by [548]" (erdosproblems.com/557), open. - concept/regularity-method — Szemerédi regularity lemma + embedding lemma, the core tool behind the unpublished AKSS claim and all its rigorous descendants (Besomi–Pavez-Signé–Stein arXiv:1906.10219, Davoodi et al. arXiv:2603.17755). - concept/absorption-method — used alongside regularity in the bounded-degree tree-embedding proofs (arXiv:1906.10219, arXiv:2409.15191) to handle leftover/boundary vertices exactly. - concept/hyperstability-structure-theorem — Pokrovskiy's arXiv:2409.15191 technique: deleting $o(|G||T|)$ edges from a $T$-free graph to bound component covers by $3|T|$, converting sparse-$T$-free to dense-$T$-free questions; the key device that finally published the bounded-degree case of Erdős–Sós. - concept/extremal-tree-embedding — the general "minimum-edge-count forces every $k$-edge tree" problem class that #548 is the flagship instance of (cf. Erdős–Gallai [ErGa59] matching threshold as the base case). - concept/degree-sequence-tree-embedding — the Klimošová–Piguet–Rozhoň strengthening (minimum degree $k/2$ + enough degree-$k$ vertices $\Rightarrow$ every $k$-edge tree embeds), proved asymptotically for dense graphs in arXiv:2603.17755, from which the degree-restriction-free asymptotic Erdős–Sós corollary is derived. - solved/erdos-sos-spiders — Fan, Hong, Liu, arXiv:1804.06567 (2018): full proof of Erdős–Sós for all spiders (trees with $\leq1$ vertex of degree $>2$), the most recent fully-closed named tree-family case; technique = explicit greedy/local embedding exploiting the single-high-degree-vertex structure. - solved/erdos-sos-bounded-degree-large-trees — Pokrovskiy, arXiv:2409.15191 (2024): Erdős–Sós fully proved for large, bounded-maximum-degree trees (sparse and dense host graphs), via the hyperstability structure theorem; the strongest rigorous partial resolution to date.