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$.

| cite | improve this answer | |
  • $\begingroup$ 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? $\endgroup$ – ameerosein Feb 21 '19 at 23:40
  • $\begingroup$ 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. $\endgroup$ – Misha Lavrov Feb 21 '19 at 23:56
  • $\begingroup$ Oh sorry I mean $\alpha=0.5$ or 50 percent $\endgroup$ – ameerosein Feb 22 '19 at 20:25
  • $\begingroup$ 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). $\endgroup$ – Misha Lavrov Feb 22 '19 at 20:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.