Proof for k-connectedness of random graphs I am really new to the theory of random graphs. It seems a lot of articles take for granted that:
For $k\in\mathbb{N}\setminus\{0\}$ and $p\in(0,1)$ fixed, almost every graph in $G(n,p)$ is $k$-connected
I was wondering how it could be proved. Does anyone know? Or where I can find such proof in the litterature?
 A: This proof is taken from Diestel R., Graph Theory:
It begins by defining property: given $i,j\in\mathbb{N}$, let $\mathscr{P}_{i,j}$ denote the property that the graph considered contains, for any disjoint vertex sets $U,W$ with $|U|\leq i$ and $|W|\leq j$, a vertex $v\notin U\cup W$ that is adjacent to all the vertices in $U$ but to none in $W$.
Lemma 11.3.2 $\textit{For every constant p}\in (0,1) \textit{and } i,j\in\mathbb{N},\textit{almost every graph } G\in\mathscr{G}(n,p) \textit{has property } \mathscr{P}_{i,j}$
Proof: For fixed $U,W$ and $v\in G-(U\cup W)$, the probability that $v$ is adjacent to all the vertices in $U$ but to none in $W$, is
$$p^{|U|}q^{|W|}\geq p^i q^j$$
Hence, the probability that no suitable $v$ exists for these $U$ and $W$ is
$$(1-p^{|U|}q^{|W|})^{n-|U|-|W|}\leq (1-p^iq^j)^{n-i-j}$$
(for $n\geq i+j$), since the corresponding events are independent for different $v$.  As there are no more than $n^{i+j}$ pairs of such sets $U,W$, the probability that some such pair has no suitable $v$ is at most
$$n^{i+j}(1-p^iq^j)^{n-i-j}$$
which tends to zero as $n\to\infty$ since $1-p^iq^j<1$
Corollary 11.3.3 For every constant $p\in(0,1)$ and $k\in\mathbb{N}$, almost every graph in $\mathscr{G}(n,p)$ is $k$-connected.
By Lemma 11.3.2, it is enough to show that every graph in $\mathscr{P}_{2,k-1}$ is $k$-connected.  Any graph in $\mathscr{P}_{2,k-1}$ has order at least $k+2$, and if $W$ is a set of fewer than $k$ vertices, then by definition of $\mathscr{P}_{2,k-1}$ any other two vertices $x,y$ have a common neighbor $v\notin W$; in particular, $W$ does not separate $x$ from $y$.
