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.

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 $Tr$ 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 runtime. For a labeled tree $T$, let $N(T)$ be the number of distinct subtrees. Fix a leaf $v$ of $T$. Then $N(T) = N(Tv) + N_1(T, v)$. Thus, again we get a recursive algorithm with a bound of $O(n^3)$ on the runtime. It might be possible to get better bounds on the runtime 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)$. 


Paul's idea can be improved into a linear algorithm to count the subtrees of a tree. Arbitrarily root the tree at some vertex $r$ and let $T_x$ denote the subtree rooted at vertex $x$. Define $A(x)$ to be the number of subtrees of $T_x$ that include $x$, and define $B(x)$ to be the number of subtrees of $T_x$ that don't include $x$. Do not include the null subtree in $B(x)$ (add 1 to the final answer if you want). If $x$ is a leaf then $A(x)=1$ and $B(x)=0$. If $y_1,\ldots,y_k$ are the children of a nonleaf $x$, then \begin{align*} A(x) &= \prod_{i=1}^k (1+A(y_i)) \\\\ B(x) &= \sum_{i=1}^k (A(y_i) + B(y_i)), \end{align*} and the answer is $A(r)+B(r)$. The two recurrences need to be applied once for each vertex. The time required for vertex $x$ is $O(1+\text{degree of }x)$, which adds up to $O(n)$ when summed over all $x$. So the total time is $O(n)$. Here we are cheating slightly by counting arithmetic operations as $O(1)$ even though numbers with a linear number of bits might be involved. This is most unlikely to be original. 

