k-connectivity in random undirected graphs (Q1059644)

It is shown that a random graph \(G_{n,p}\) of Erdős-Renyi type, with \(p\geq c/n\), has a giant k-block almost surely, for any constant \(k>0\). Bounds are given on the distribution of the size of the giant k-block for \(p\geq c\) log n/n.