# sampling a connected graph to a smaller connected graph

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$$.
• I am confused! $\alpha$ is fixed and the size of the graph $n$ is fixed as well. I have a random yet connected graph of let's say 500 nodes that has let's say 0.5 percent of the edges possible (or the chance of two nodes being connected is 0.5). I want to see how small (on average) the connected subsampled graph could be. Can I make a vertex-induced subgraph of let's say 40 vertices and be confident that this subgraph is still connected? – ameerosein Feb 21 '19 at 23:40
• Now I am also confused. What do you mean, then, by "with high probability"? Usually, in the study of random graphs, it means "with probability tending to 1 as (some parameter) goes to $\infty$". Still, in your case, $\alpha = \frac1{200}$ is much smaller than $\frac{\ln 40}{40}$, so we don't expect a typical $40$-vertex induced subgraph to be connected. – Misha Lavrov Feb 21 '19 at 23:56
• Oh sorry I mean $\alpha=0.5$ or 50 percent – ameerosein Feb 22 '19 at 20:25
• Then $\frac1\alpha \ln \frac1\alpha = 2\ln2$ is very small, so we don't get precise lower bounds on $n'$ from the asymptotic bounds. However, a random subgraph on just $3$ vertices has a $\frac12$ chance of being connected; a random subgraph on $4$ vertices has a $\frac{19}{32}$ chance, and so on. For $40$ vertices, it is almost certain, because $\alpha = \frac12$ is much larger than $\frac{\ln 40}{40}$. As before, this does not depend on $n$, only on $n'$ (assuming we start with a randomly chosen graph). – Misha Lavrov Feb 22 '19 at 20:43