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 oriented tree whose edges all point away from its root. Reversing every edge gives an in-arborescence. An $n$-vertex arborescence embeds in every tournament on $2n-2$ vertices: repeatedly extend an outward leaf in a half-sparse median-order embedding. Reversal gives the analogous existence statement for in-arborescences.