Are there any results on the number of subgraphs in a labeled tree (or a general labeled graph)? I would also be happy to know any results on the number of subgraphs in an unlabeled tree. Cayley's formula says how many different trees I can form given n vertices, but it doesn't seem to relate to the problem of counting subgraphs in a given tree. Any help is appreciated.



Counting the number of subgraphs in a given labeled tree
The following algorithm should efficiently calculate the answer for the number of subtrees of a labeled graph.


Let $(T, r)$ be a labeled, rooted tree with root $r$. We first calculate the number of subtrees containing $r$. Call this value $N\_1(T, r)$. If $r\_1, \dots, r\_k$ are the neighbors of $r$ and $T\_1,\dots, T\_k$ are the trees of $T-r$ such that $r\_i \in V(T\_i)$ for $1 \le i \le k$, then 


$N\_1(T, r) = \prod\_1^k \left( N\_1(T\_i, r\_i) + 1 \right).$


This follows because for each neighbor $r\_i$ of $r$, we have a choice of $N\_1(T\_i, r\_i)$ possible trees or alternatively, the empty tree. 


This formula gives a recursive algorithm to calculate $N\_t(T, r)$. Since the total number of vertices in the trees decreases in each iteration of the algorithm, we get an easy $O(n^2)$ bound on the run-time. 


For a labeled tree $T$, let $N(T)$ be the number of distinct subtrees. Fix a leaf $v$ of $T$. Then $N(T) = N(T-v) + N\_1(T, v)$. Thus, again we get a recursive algorithm with a bound of $O(n^3)$ on the run-time. It might be possible to get better bounds on the run-time of the algorithms. 


The specific value of $N(T)$ will depend a lot on the tree $T$. For example, if $T$ is the path on 
$n$ vertices, then $N(T) = O(n^2)$. Alternatively, if $T$ is the star on $n$ vertices, then $N(T) = O(2^n)$. 


