# Upper bound on the number of subgraphs in a tree

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.

• Sorry, I missed the crucial word "acyclic", which resolved all ambiguity! I would suggest simply replacing "connected acyclic graph" with "tree" in any case. – j_random_hacker May 3 at 2:04
• 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 – Bernardo Subercaseaux May 3 at 2:17
• If a tree has $n$ vertices then it has $n-1$ edges. – 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.