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. Here, antidirected means that every graph
vertex is a local source or a local sink.
The proof in Frederickson (2026) is based on the original
proof generated by GPT-6 Astra.
