Does a bounded branching/log depth dihotomy hold for rooted trees?

Question

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)$.

Answer 1

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.$$