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!


1 Answer 1


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

  • $\begingroup$ Is there any upper bound on this number? $\endgroup$
    – zack
    May 3, 2021 at 2:14
  • $\begingroup$ The obvious upper bound is $2^n$. $\endgroup$ May 3, 2021 at 6:33
  • $\begingroup$ Hi @YuvalFilmus, is there any reference somewhere for this formula ? I'll be using it in a paper and want to give credit. $\endgroup$ May 25, 2022 at 9:11
  • $\begingroup$ Not that I’m aware of, but it’s plausible that you can find it somewhere. $\endgroup$ May 25, 2022 at 9:16
  • $\begingroup$ I searched but couldn't find anything either. Thank you. $\endgroup$ May 25, 2022 at 13:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.