 Arborescence (graph theory)

An arborescence is a rooted tree with each edge oriented away from its root. There is a unique directed path from the root to every vertex; equivalently the root has indegree zero and every other vertex has indegree one. Reversing all edges gives an in-arborescence, with unique directed paths toward the root.

For $n\ge 2$, every $n$-vertex arborescence embeds in every tournament on $2n-2$ vertices. The half-sparse median-order embedding proves this by repeatedly extending an outward leaf. Reversing the tournament and the arborescence gives the corresponding in-arborescence statement. The restriction $n\ge 2$ matters: a one-vertex arborescence needs a nonempty host, while $2n-2=0$ would give an empty host.