Number of subtrees of a tree Define a subtree to be any connected subgraph of a tree.
Prove that the number of subtrees of a complete binary tree is not polynomial
in the number of nodes.
Give an example of a class of trees $\{T_n\}$ where the number of subtrees is a
polynomial in the number of nodes.
Thoughts:
This function seems to give us the number of special trees, given the root.
$$F(n) = 1 + 2 f(\text{left subtree}) + 2  f(\text{right subtree}) + f(\text{left subtree})  f(\text{right subtree})$$
 A: You don’t need to worry about the exact number of subtrees of a complete binary tree. (I use the term complete binary tree to mean one in which every non-leaf has two daughters, and all levels are filled; it’s sufficient to look at those even if you use the definition that doesn’t require the last level to be filled.) If $T_n$ is the complete binary tree of height $n$ (or depth $n$, if that’s your terminology), then $T_n$ has $2^{n+1}-1$ vertices. Let $T_n^L$ and $T_n^R$ be the left and right subtrees of $T_n$. Each is a copy of $T_{n-1}$ and therefore has $2^n-1$ vertices. Let $T$ be a subtree of $T_n^L$ and $v$ a vertex of $T_n^R$; there is a unique path in $T_n$ from the root of $T$ to $v$, and adding that path to $T$ produces a subtree $S(T,v)$ of $T_n$. If $T,T'$ are subtrees of $T_n^L$, and $v,v'$ are vertices of $T_n^R$, then $S(T,v)=S(T',v')$ iff $T=T'$ and $v=v'$. Use this to show that if $T_n$ has $t_n$ subtrees, then
$$\lim_{n\to\infty}\frac{t_{n+1}}{t_n}=\infty$$
and conclude that $t_n$ cannot be a polynomial in $n$ (why?).
For the second question, note that every chain is a tree.
