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.
[Math] Counting the number of subgraphs in a given labeled tree
co.combinatoricstrees
Best Answer
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)$.