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.
How many connected induced subgraphs does a hypercube of dimension n have
combinatoricsgraph theory
Best Answer
An exact count is tough to obtain. You can find the first few values in OEIS sequence A290758.
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$.