The Erdős-Sós theorem states that for every integer 
, every graph of average vertex degree greater than 
contains every tree having 
edges as
a subgraph. The bound is sharp for a disjoint
union of complete graphs of order 
.
Frederickson (2026) gave a simplified proof using random cyclic orderings and also proved the stronger directed statement that every directed
graph of average outdegree greater than 
contains every antidirected oriented
tree with 
arcs. The proof in Frederickson (2026) is based on the
original proof generated by GPT-6 Astra.
