# 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) &= \sum_{i=1}^\ell (A(T_i) + B(T_i)) \\ B(T) &= \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).

• Is there any upper bound on this number?
– zack
May 3 at 2:14
• The obvious upper bound is $2^n$. May 3 at 6:33