I have a graph $G$ which has $n$ nodes and $\alpha*(n^2-n)/2$ edges (so the chance of having edge $(i,j)$ is $\alpha$). The graph is connected which means that if we calculate the number of components it results in 1.
I want to randomly select some nodes of the graph and make a new vertex-induced graph (those nodes plus the edges between them from the original graph) so the new sub-sampled graph stay connected with a high probability. I am looking for the largest possible sub-sampling rate for this task (or the smallest graph size which meets the connectivity condition on average). In other words, I am wondering how small could it be while still connected.
I know that under some circumstances there would be a cut vertex or some major vertices which removing them will remove the connectivity in the new graph, but I am looking for the average as I am want to do
If you start with a binomial random graph with $n$ vertices and edge probability $\alpha$, and then sample $n'$ vertices uniformly at random, then the result is equivalent to just taking a binomial random graph with $n'$ vertices and edge probability $\alpha$.
When $n'$ is large (equivalently, when $\alpha$ is small), the threshold for connectivity is $\alpha \approx \frac{\ln n'}{n'}$ (which can be made more precise), or equivalently $n' \approx \frac1{\alpha} \ln \frac1{\alpha}$.
The subgraph with this many vertices is connected with high probability as $\alpha \to 0$, which might not be exactly the statement you want. If $\alpha$ is constant and $n \to \infty$, then we can take $n'$ to be any function that grows with $n$ and have the subsampled graph be connected with high probability as $n \to \infty$.