Is there an upper bound of the number of induced subgraphs in a tree (i.e., connected acyclic undirected graph)? The bound can be expressed in terms of vertices, edges, etc.

For example, consider the following graph $G$ represented as edge list: $\{(S,T),(T,G),(T,B),(B,H),(H,Q)\}$. The number of connected subgraph (i.e., tree) is (represented by the set of vertices): $\{S\}$, $\{T\}$, $\{G\}$, $\{B\}$, $\{S,T\}$, $\{T,G\}$, $\{T,B\}$, $\{S,T,G\}$, $\{B,T,G\}$,$\{S,T,B\}$, $\{S,T,G,B\}$, $\{T,G,B,H\}$,$\{T,B,H,Q\}$, $\{S,T,B,H\}$,$\{S,T,B,H,G\}$,$\{T,G,B,H,Q\}$,$\{S,T,B,H,Q\}$, and $\{S,T,B,H,G,Q\}$.

I find two seemingly relevant answer that can directly answer my questions 1 and 2 but I'm not sure.

  • 1
    $\begingroup$ Sorry, I missed the crucial word "acyclic", which resolved all ambiguity! I would suggest simply replacing "connected acyclic graph" with "tree" in any case. $\endgroup$ – j_random_hacker May 3 at 2:04
  • $\begingroup$ Probably taking a depth-n, perfect k-ary tree is a good place to start. If you call F(n,k) its number of connected subgraphs, and G(n, k) to those who include the root, then you have something like: F(n, k) = k*F(n-1, k) + \sum_{i=1}^k (k choose i) G(n-1, k)^i $\endgroup$ – Bernardo Subercaseaux May 3 at 2:17
  • $\begingroup$ If a tree has $n$ vertices then it has $n-1$ edges. $\endgroup$ – Yuval Filmus May 3 at 7:20

Let us prove by induction that any tree on $n$ vertices has at least $2^{n-1} - n$ induced disconnected subgraphs.

When $n = 1$, this is clear since $2^{n-1} - n = 0$. Now suppose $n > 1$, and let $T$ be a tree on $n$ vertices. Choose an arbitrary leaf $v$, let $T'$ be the tree obtained by removing $v$, and suppose that $v$ is connected to $u \in T'$. By induction, $T'$ has at least $2^{n-2} - (n-1)$ induced disconnected subgraphs. Each of these correspond to two induced disconnected subgraphs of $T$, one including $v$ and one not including $v$. Moreover, for any $w \in T'$ different from $u$, the subgraph induced by $\{v,w\}$ is disconnected, and does not arise from an induced disconnected subgraph of $T'$ (since the subgraph of $T'$ induced by $\{w\}$ is connected). In total, we get this many induced disconnected subgraphs of $T$: $$ 2(2^{n-2} - (n-1)) + (n-2) = 2^{n-1} - 2(n-1) + (n-2) = 2^{n-1} - n. \quad \square $$

This is tight, as the example of a star shows. If the center of the star is $x$ and the other vertices are $y_1,\ldots,y_{n-1}$, then the subgraph induced by any subset of $\{y_1,\ldots,y_{n-1}\}$ of size at least 2 is disconnected. There are $2^{n-1} - (n-1) - 1 = 2^{n-1} - n$ of these.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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