= Three-times-order tournament bound for oriented trees
{title2=$|V(T)|=n\ge2\Longrightarrow T\subseteq\text{every }(3n-3)\text{-vertex tournament}$}
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.
Back to article page
