Sample a random subgraph from an undirected, unweighted graph, what's the probability of "every two nodes's distance is at least 3 in the subgraph"?

Question

This may be a problem in sampling theory or graph theory. I have done many research but I still didn't find valid solutions.

I know a simple random sample is representative of the population. Now I wonder if it still works when it's 'restricted' by a social network, which means if there are two nodes' distance is less than 3, it can not be chosen as the sample. I'd like to know under which condition, every two nodes in a simple random sample has distance at least 3 in high probability.

In detail, consider a undirected unweighted graph $G=(V,E)$, where $V=\{1,\dots,n\}$ is the vertex set and E is the edge set. Consider a simple random sample $S\subseteq V$, and let $|S|$ indicate the number of set $S$. Now we ask: under which condition (like the restiction on $|S|$, the pattern in which $G$ goes to infinity, the restriction on $G$, etc), $$P(d(i,j)\geq3,\forall i,j\in S) \to 1.$$

It is better if there are non-asymptotic properties.

Answer 1

Suppose there is a bound $b$ on $$\frac{|S|}{\sqrt{|G|/\ln|G|}}$$ and a bound $k$ on the number of vertices within distance 3 of a vertex. Then as the graphs get larger, the probability goes to $1$ that all vertices in the subgraph have distance at least 3 between them.

For instance, suppose that for each $n$, the graph is an $n\times n$ chessboard where the edges are knight’s moves, and $S$ is chosen with $n/\log_{10}n$ vertices. Then we can take $b=1$, $k=76$ and the result holds.

The proof is just an asymptotic analysis of the fraction of graphs with the desired property, which is at least $$\prod_{i=1}^{|S|}\frac{n-k|s|+ik}{n-|s|+i}.$$