# Vertex connectivity of random graphs?

Consider simple, undirected Erdős–Rényi graphs $$G(n,p)$$, where $$n$$ is the number of vertices and $$p$$ is the probability for each pair of vertices to form an edge. Many properties of these graphs are known - in particular, $$G(n,p)$$ is almost surely connected when $$p \gt (1 + \epsilon)\frac{\log(n)}{n}$$, and the largest clique in $$G(n, \frac{1}{2})$$ is almost surely about $$2\log_2(n)$$.

What is known about the vertex connectivity number $$\kappa(G)$$, $$G\in G(n,p)$$, the minimum number of vertices that one must remove in order to disconnect the graph?

It is known that for fixed $$k$$ and fixed $$p\in (0,1)$$, almost every graph in $$G(n,p)$$ is $$k$$-connected, but what is the expected connectivity as a function of $$p$$ and $$n$$?

• Yes, you are correct. Jun 16, 2010 at 0:42

The expected connectivity cannot be higher than the expected minimal degree, which jumps to roughly $$pn$$ after getting into the range $$p\gg\frac{\log n}{n}$$. On the other hand, sloppily counting potential clusters of size $$m < n/2$$ that have boundaries of less than $$k$$ vertices gives a probability of $$\binom{n}{m}\binom{n-m}{k}(1-p)^{m(n-m-k)}$$, which is for $$k \ll n$$ decreasing in $$m$$ up to $$m\approx \frac{n-k}{2}$$ and increasing after that value, so we can get an estimate by considering only $$m=1$$ (checking for vertices with at most $$k$$ neighbours) and $$m=\frac{n}{2}$$: $$\binom{n}{n/2}\binom{n/2}{k}(1-p)^{n(n-2k)/4} < \exp(n \log 2+k \log n - pn(n-2k)/4) <$$ $$< \exp(n \log 2 - pn(\frac{n}{4}-\frac{k}{2}-\log n)) < \exp(-\frac{n \log n}{4} + n \log 2 +2(\log n)^2),$$ this latter number tending to $$0$$ fast enough to ignore it. So, the expected connectivity is the expected minimal degree and is roughly $$pn$$ once $$p$$ exceeds $$\log n/n$$. Do you need the behaviour of expected connectivity specifically in this region?
• Thanks Thorny - this was very helpful. So the $E(\kappa(H))$ tends to around $\frac{n}{2}$ for $H \in G(n,p)$, which is what I was most interested in. Jun 16, 2010 at 15:08