Lower bound on the number of "short" paths in a rooted tree with polynomial size
The lower bound is $\Omega(\log n)$ paths with $O(\log n)$ branching nodes, if you have at least $\Omega(\log n)$ branching nodes in the tree.

This can be achieved: use a tree which has one long path (length $n$) all of whose nodes are branching nodes, with no other branching nodes in the tree.

Here is a sketch of the lower bound.

First, compactify the tree by contracting any interior node that isn't a branching node. If the original size of the tree was $&lt; n^c$, the new tree must still be $&lt; n^c$, since you've only reduced the number of nodes. Now, the depth of a leaf is the number of branching nodes on the original path to that leaf, and we have a complete binary tree (every node has either degree 2 or 0). 

If there are no leaves of depth $\Omega(\log n)$, then the number of paths is one more than the number of branching nodes, which is $\Omega(\log n)$, so we can assume that at least one leaf has depth $\Omega(\log n)$. 

Next, recall Kraft's inequality. If the depth of a leaf in a complete binary tree is $d(v)$, then $\Sigma_{v \mathrm{\ leaf}} 2^{-d(v)} = 1$. 

Now, we have fewer than $n^c$ leaves. We want to show that we have a lot of them at depth $O(\log n)$. Suppose we eliminate from consideration the ones that are depth at least $\log_2(n^{c+1}) = (c+1) \log_2 n$. This removes at most weight $1/n$ from the sum in Kraft's inequality, so for those leaves $v$ at depth at most $d(v)\leq (c+1) \log_2 n$, we have $\sum_{v\mathrm{\ low \ depth \ leaf}} 2^{-d(v)} &gt; 1-\frac{1}{n}$.  We also have $\sum_{v\mathrm{\ low\ depth\ leaf}} 2^{-d(v)} &lt; 1$ (since at least one leaf has depth too large to be included in this sum). 

It's fairly easy to show that to get a sum of numbers $2^{-k}$ strictly between $1$ and $1-\frac{1}{n}$, we need at least $\log_2 n$ of them. This shows that there are $\Omega(\log n)$ paths with $O(\log n)$ branching nodes.