# 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.

-
Do you mean connected subgraphs? Otherwise it seems trivial. –  Brendan McKay Jan 27 '12 at 12:32
@Brendan, how does allowing the subgraphs to be disconnected make things trivial? When I count the number of subgraphs of trees consisting of n-point paths, for example, I get the every-other-Fibonacci sequence 2,5,13,34,89,.... That doesn't seem deep, but it doesn't feel trivial. Or am I not understanding the problem? –  Barry Cipra Jan 27 '12 at 18:59
My take is (since the vertices are labeled) the number of subgaphs is about 2^E, where E is the number of edges in the original graph. Brendan may have something deeper in mind than this though. Gerhard "Ask Me About System Design" Paseman, 2012.01.27 –  Gerhard Paseman Jan 27 '12 at 19:21
@Gerhard, if you retain all the vertices, then the number of subgraphs is clearly 2^E. But as you erase edges, you're also allowed to erase certain vertices, which is why my n-point path example produces something asymptotically proportional to phi^2n. –  Barry Cipra Jan 27 '12 at 19:32
Yes. Do you retain the labels? If you do, the answer is still 2^E. Gerhard "Ask Me About System Design" Paseman, 2012.01.27 –  Gerhard Paseman Jan 27 '12 at 19:52

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)$.

-
This is also what I came up when putting some time towards the problem. Basically, star is the worst case with O(2^n) different subgraphs, and I was mainly interested in the worst case behavior. I think it's also possible to show an O(2^n) bound for a complete binary tree. –  filox Jan 27 '12 at 23:15

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.

-