Source-linked AI summary
The Erd\H{o}s--S\'os Theorem
David R. Wood
TL;DR
For every integer t ≥ 2, every graph with average degree greater than t − 2 contains every tree with t vertices. A counting argument shows that a graph omitting T has average degree at most t−2. Every graph with average degree greater than t−2 contains every tree on t≥2 vertices.
Problem
For every integer t ≥ 2, every graph with average degree greater than t − 2 contains every tree with t vertices.
Source: §1 · p. 1Method
A counting argument shows that a graph omitting T has average degree at most t−2.
Source: §2 · p. 2Results
Every graph with average degree greater than t−2 contains every tree on t≥2 vertices.
Source: §1 · p. 1Takeaways & Limitations
The threshold is best possible, since the complete graph on t−1 vertices has average degree t−2 and contains no tree on t vertices.
Source: §1 · p. 1
Abstract
from arXiv · showhide
We present an exposition of a proof, discovered by GPT-6 Astra, of the Erd\H{o}s--S\'os Conjecture, which states that every graph with average degree greater than $t-2$ contains every tree on $t\geq 2$ vertices.
1 Introduction
The Erdős–Sós Theorem states that average degree greater than t−2 guarantees every tree on t≥2 vertices. This section presents an exposition of the proof and places the result in context, including its Ramsey application.
1 Introduction
- Average degree greater than t−2 guarantees every tree on t≥2 vertices, and the threshold is best possible.The complete graph on t−1 vertices has average degree t−2 but contains no tree on t vertices.Source: §1 · p. 1
- The paper expounds GPT-6 Astra’s proof of the conjecture, which was formally verified in Lean.The proof was discovered as part of the FrontierMath Erdős project.Source: §1 · p. 1
- The theorem improves the greedy embedding bound from average degree at least 2t−2 to greater than t−2.The 2t−2 bound follows by first finding a subgraph of minimum degree at least t−1.Source: §1 · p. 1
- Earlier, a proof for sufficiently large t was announced using the Szemerédi Regularity Lemma, but had not been written in full as far as the author was aware.The conjecture also prompted partial results for families of trees, host graphs, and relative tree and host sizes [6] [30] [33] [31] [32].Source: §1 · pp. 1–2
- In a k-edge-coloring of K_n with n=k(t−2)+2, the argument bounds each color’s edges assuming no monochromatic T, then derives a contradiction.The per-color bound is (t−2)n/2.Source: §1 · p. 2
2 The Proof
The proof counts vertex orderings that expose an edge and rooted tree embeddings within their prefixes, then uses induction on tree size to derive the Erdős–Sós threshold.
2 The Proof
- The proof counts edge-marked vertex orderings in M(G) and records which prefixes contain a rooted copy of T in R(T, r).Each edge contributes 2(n −1)! pairs to M(G).Source: §2 · p. 2
- If G contains no T, then R(T, r) is empty, so the counting bound implies 2m/n ≤ t −2.This is the contradiction bound used to establish the theorem's strict average-degree threshold.Source: §2 · p. 2
- If a graph has average degree greater than t −2, it contains every tree with t vertices.The proof derives the contrapositive bound that a graph containing no such tree has average degree at most t −2.Source: §2 · p. 2
- When r is a leaf, reversing an ordering prefix yields an injection that bounds |R(T −r, r′)| by |R(T, r)| + n!.At most one earliest qualifying index per ordering is excluded, contributing the n! allowance.Source: §2 · pp. 2–3
- When r is not a leaf, splitting T into subtrees T1 and T2 at r gives |R(T1, r)| + |R(T2, r)| ≤ |M(G)| + |R(T, r)| + n!.A segment-reordering injection sends exceptional T1-prefixes outside R(T2, r), with at most n! excluded pairs.Source: §2 · pp. 3–4
- Induction handles leaf roots by deleting a leaf and non-leaf roots by splitting T at r, combining the two cases to bound |M(G)|.The leaf case uses Lemma 3; the split case applies the bound for two smaller subtrees and Lemma 4.Source: §2 · p. 4