Let $T$ be a rooted tree. For any subtree $T' \subset T$ write $L(T')$ for the number of leaves of $T'$.


Further, for $T' \subset T$ define the *branch-depth* of a node $v \in T'$ as the number of nodes $w$ on the path from $v$ to $root(T')$ having more than a single child. The branch depth of $T'$ is then the maximal branch-depth of its leaves.


Let's call a tree binary if each node has at most two children. 


I wonder if something along the following lines is true. There is constant $c > 0$ such that for any tree $T$ with $N$ leaves there is a subtree $T$ with $L(T) \geq N^{c}$ which is either binary or has branch-depth $O(\log N)$.



Does a bounded branching/log depth dihotomy hold for rooted trees?
Call a tree on $x$ vertices *low* if its branch-depth is at most $\log x$.


We prove by induction that for every tree on $n$ vertices there are some numbers $a,b$ such that $n\le ab$ and the tree contains a binary subtree on $a$ vertices AND a low subtree on $b$ vertices. Suppose this is false for some $n$, and denote the size of its largest binary subtree by $a$. Denote the sizes of the trees we obtain after deleting the root by $n\_1,n\_2,\ldots$, so $\sum n\_i=n-1$. By induction, in the $i$'th subtree we have a binary tree on $a\_i\le a$ vertices and a low subtree on $b\_i$ vertices for some $n\_i/a\_i\ge b\_i<n/a$. 


Now fix some index, say 1. Merging the largest binary subtrees of the first and $i$-th tree would give a binary tree of size $a\_1+a\_i+1\le a$. Since $a\_1>an\_1/n$, this gives $a\_i<a(1-n\_1/n)$. Let us see what happens if we merge the low subtrees on $b\_i$ vertices. The branch-depth of the new subtree is $\max\_i b\_i+1$, and it has $1+\sum\_i b\_i$ vertices. If we can show that $1+\sum\_i b\_i\ge 2b\_1$, then we know that this new subtree is also low and we are done as $1+\sum\_i b\_i\ge 1+\sum n\_i/a\ge n/a$. But $1+\sum\_i b\_i\ge 2b\_1$ holds, as


$$\sum\_{i>1} b\_i\ge \sum n\_i/a\_i>\sum n\_i/(a(1-n\_1/n))=(n-n\_1)/(a(1-n\_1/n))=n/a>b\_i.$$


