= Solution
If the <random k-out graph> with $k=2$ is disconnected, one of its <connected components of a graph> has size $3\le s\le n/2$. The lower bound follows because every <vertex> chooses two distinct neighbours inside its component. For a specified $s$-set $S$, absence of crossing <edges> requires every choice at a <vertex> in $S$ to stay in $S$, and every choice outside to stay outside. Independence of choices at different <vertices> gives exactly
$$
\Pr(S\text{ has no crossing edge})=\left[\frac{\binom{s-1}2}{\binom{n-1}2}\right]^s\left[\frac{\binom{n-s-1}2}{\binom{n-1}2}\right]^{n-s}.
$$
For $3\le s\le n/2$, the two ratios are at most $(s/n)^2$ and $(1-s/n)^2$. Indeed each of the factors $(s-j)/(n-j)$, $j=1,2$, is at most $s/n$, and the complementary statement is identical. Put $t=s/n$. The <binomial coefficient> bound $\binom ns\le t^{-s}(1-t)^{-(n-s)}$ follows by bounding the <probability> of $s$ successes in $\operatorname{Bin}(n,t)$ by one. Thus the <union bound> gives
$$
\Pr(G_{2\text{-out}}\text{ disconnected})\le\sum_{s=3}^{\lfloor n/2\rfloor}t^s(1-t)^{n-s}\le\sum_{s=3}^{\lfloor n/2\rfloor}(s/n)^s.
$$
For $s\le\sqrt n$, the last summands are at most $n^{-s/2}$, whose sum from three tends to zero. For $s>\sqrt n$, they are at most $2^{-s}$, again summing to zero. Therefore
$$
\boxed{\Pr(G_{2\text{-out}}\text{ connected})=1-o(1).}
$$
The proof bounds all possible small components rather than assuming the dependent undirected <edges> behave like a <binomial random graph>.
Back to article page
