Counting the number of subgraphs in a given labeled tree 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.
 A: 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 non-leaf $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.
A: 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)$.  
