In a simple graph, there are $n$ vertices each has exactly $k \ll n$ edges, chosen randomly (details below). What is the expected value of the number of connected induced subgraphs? Or: what reduction can be made to this problem to make it easier to compute? For example $n=2^{30}$, $k=100$ can be assumed.
The graph is constructed in the following way:
- Generate $n$ vertices.
- Out of all vertices with $m < k$ edges, pick one randomly (uniform distribution) $v$.
- Out of all other vertices with less than $k$ edges, pick $k-m$ and connect them with $v$. (At the end, if there are less than $k-m$ connect all of those got left. I think this should not change the result much as $k-m \ll n$)
- Go back to step 2 until exhausted.