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