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

  • $\begingroup$ Perhaps this sort of argument can help mathoverflow.net/questions/280505/… $\endgroup$
    – DmitryZ
    Mar 22, 2019 at 13:29
  • $\begingroup$ Is the branch-depth of a tree the maximum branch-depth of a vertex, or the minimum? $\endgroup$ Mar 28, 2019 at 12:54
  • $\begingroup$ Thanks for the comment! It's the maximum over the leaves, edited the question. $\endgroup$
    – DmitryZ
    Mar 28, 2019 at 15:50
  • $\begingroup$ Edited the conjecture into a more uniform statement $\endgroup$
    – DmitryZ
    Mar 28, 2019 at 16:09
  • $\begingroup$ By binary tree, do you mean that every node should have at most two children? $\endgroup$
    – domotorp
    Mar 29, 2019 at 8:17

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

  • $\begingroup$ I’m not sure I follow the step when the root is deleted. Note that in the conjecture the “size” $L(T)$ is not the number of vertices but the number of leaves. $\endgroup$
    – DmitryZ
    Mar 30, 2019 at 12:27
  • $\begingroup$ @DmitryZ Right, vertices should read as leafs throughout my answer, and ignore a few $\pm 1$'s. Why is the deletion of the root not clear? After you delete it, the tree falls apart to smaller trees. $\endgroup$
    – domotorp
    Mar 30, 2019 at 14:37
  • $\begingroup$ Gotcha. I was confused by +/- 1ones, but modulo minor (I believe there should be $max_i \log b_i$) edits I think the argument is correct! $\endgroup$
    – DmitryZ
    Mar 31, 2019 at 11:29
  • $\begingroup$ @DmitryZ Indeed, you're right about that too! I can see that you've accepted my answer, maybe you've forgotten that you have to award the bounty separately. $\endgroup$
    – domotorp
    Mar 31, 2019 at 12:23
  • 1
    $\begingroup$ @MISC {326736, TITLE = {Does a bounded branching/log depth dihotomy hold for rooted trees?}, AUTHOR = {Dömötör Pálvölgyi (mathoverflow.net/users/955/domotorp)}, HOWPUBLISHED = {MathOverflow}, NOTE = {URL:mathoverflow.net/q/326736 (version: 2019-03-30)}, EPRINT = {mathoverflow.net/q/326736}, URL = {mathoverflow.net/q/326736} } $\endgroup$
    – domotorp
    Mar 31, 2019 at 19:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.