Oriented tree

An oriented tree is an orientation of every edge of an undirected tree. Its arrows need not all point towards, or away from, any one root. It is acyclic as a directed graph, but different orientations can have different embedding behaviour in tournaments.

For a source-rooted oriented tree, let $b$ count edges pointing towards the root and let $c$ count nonempty connected components formed by those edges. A half-sparse median-order embedding exists in $2n+2(b-c)$ vertices. Remove forward leaves, or remove a terminal backward component of order $m$ and replace it temporarily by $2m-2$ outward leaves. Their images contain an in-arborescence copy of the component. Choose the direction and root to minimize $(b-c,b)$ lexicographically; this makes the root a source and gives $b-c\le (n-3)/2$ unless the tree is already an arborescence. The stated bound follows.

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.