Upper bound on the number of subgraphs in a tree
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 &gt; 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.