TOPICS
Search

Directed Erdős-Sós Theorem

The directed Erdős-Sós theorem (Mubayi and Verstraëte 2026) states that every Eulerian digraph on n vertices and with more than (t-1)n arcs contains every oriented tree having t arcs. An Eulerian digraph has equal indegree and outdegree at every vertex. The bound is sharp.

The result is a directed analogue of the Erdős-Sós theorem for ordinary graphs. Mubayi and Verstraëte (2026) credit GPT-6 Astra with producing the proof after the authors posed the problem, and report that they checked and rewrote the argument. As of Sep. 22, 2026, independent specialist review had not been reported.

See also

Directed Graph, Eulerian Digraph, Oriented Tree

Explore with Wolfram|Alpha

References

Mubayi, D. and Verstraëte, J. "Erdős-Sós for Digraphs." 10 Sep 2026. https://arxiv.org/abs/2609.10987.

Cite this as:

Weisstein, Eric W. "Directed Erdős-Sós Theorem." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/DirectedErdos-SosTheorem.html

Subject classifications