number of connected induced subgraph in a tree Let G be a tree-structured graph. A connected induced subgraph is an induced subgraph from G that is connected. (Since the original graph is a tree, any connected induced subgraph is also a tree)

My question: Given a tree G of n vertices, how many connected induced subgraph can be obtained from G?

An example: n = 4, G looks like 1---2---3---4 (I name those four vertices by 1, 2, 3, 4). Then we have 10 connected induced subgraph. Namely, they are {1}, {2}, {3}, {4}, {1,2}, {2,3}, {3,4}, {1,2,3}, {2,3,4}, {1,2,3,4} where I represent a connected induced subgraph by a set of their vertices.

Another example: n = 4, G looks like 1---2---3, 1---2---4 (node 2 directly connects 3 and 4. forgive my poor way of drawing it in text)
In this case, we have 11 connected induced subgraph. Namely, they are {1}, {2}, {3}, {4}, {1,2}, {2,3}, {2,4}, {1,2,3}, {1,2,4}, {2,3,4}, {1,2,3,4}.

From those two little examples we can see that the actual number depends on the exact structure of the tree, so, I am hoping you can help me further determine what is the factor that influences the result (I guess the maximal degree?).

Thank you!
Let $T$ be a tree rooted at $r$. Let the children of $r$ be $r_1,\ldots,r_\ell$, and let the corresponding subtrees be $T_1,\ldots,T_\ell$.

Consider a connected induced subgraph of $T$. There are two cases:


The subgraph doesn't contain $r$. In this case, the subgraph is a connected induced subgraph of some $T_i$.
The subgraph contains $r$. In this case, for each $i$, either the subgraph contains no vertices of $T_i$, or its intersection with $T_i$ is a connected induced subgraph of $T_i$ containing $r_i$.


Let us denote the number of subgraphs of the first type by $A(T)$, and those of the second type by $B(T)$. You are interested in $A(T) + B(T)$. The description above translates to the following recurrences:
$$
\begin{align}
A(T) &amp;= \sum_{i=1}^\ell (A(T_i) + B(T_i)) \\
B(T) &amp;= \prod_{i=1}^\ell (1 + B(T_i))
\end{align}
$$
Using this, you can calculate the number of connected induced subgraphs of a tree in linear time (ignoring the cost of arithmetic).