# How many connected induced subgraphs does a hypercube of dimension n have?

Let $$Q_n$$ be the graph formed from the vertices and edges of an $$n$$-dimensional hypercube. How many connected induced subgraphs does it have?

Two connected induced subgraphs are the same if and only if they have the exact same vertices.

• Are we counting isomorphic subgraphs as distinct? (E.g. are all the two-vertex connected subgraphs, which is to say edges, counted as a single subgraph, or as many?) Mar 4, 2020 at 8:26
• No, they are not distinct. Two subgraphs are the same if and only if they have the exact same vertices. I'll update the question. Mar 4, 2020 at 8:42

For an asymptotic estimate, let's pick an induced subgraph of $$Q_n$$ uniformly at random and consider its isolated vertices. There are $$2^n$$ vertices in the graph. Each one of them is an isolated vertex with probality $$\frac1{2^{n+1}}$$: for this to happen, it must appear in the subgraph, and none of its $$n$$ neighbors can appear. So the expected number of isolated vertices is $$2^n \cdot \frac1{2^{n+1}} = \frac12$$.
For large $$n$$, these isolated vertices appear close to independently. So, we can approximate the number of isolated vertices by a Poisson variable with mean $$\frac12$$. In particular, the probability is that there are no isolated vertices should tend to $$e^{-1/2}$$ as $$n \to \infty$$.
Connected components that are bigger than an isolated vertex will be much more rare. Consider for example the $$2$$-vertex connected components: there are $$n 2^{n-1}$$ possible components like this, which is not too much bigger than the number of vertices. But the probability that one of them is a connected component of the induced subgraph is much smaller: it is $$\frac1{2^{2n}}$$. The expected number is $$\frac{n}{2^{n+1}}$$, which is tiny. As we add more vertices, this probability will fall even more quickly.
So, we can estimate the number of connected induced subgraphs of $$Q_n$$ as $$e^{-1/2} \cdot 2^{2^n}$$. This is very good for large $$n$$: for example, for $$n=5$$, this predicts $$2\,605\,029\,347$$ connected induced subgraphs, whereas the true count is $$2\,524\,817\,935$$.