For a source-rooted oriented tree, let count edges pointing towards the root and let count nonempty connected components formed by those edges. A half-sparse median-order embedding exists in vertices. Remove forward leaves, or remove a terminal backward component of order and replace it temporarily by outward leaves. Their images contain an in-arborescence copy of the component. Choose the direction and root to minimize lexicographically; this makes the root a source and gives unless the tree is already an arborescence. The stated bound follows.
Articles by others on the same topic
There are currently no matching articles.