 Connectivity of random k-out graphs

For $k=2$, a disconnected graph has a component of size $3\le s\le n/2$. The probability that a fixed $s$-set has no crossing edge is at most $(s/n{)}^{2s}(1-s/n{)}^{2(n-s)}$. The union bound and $\left(\genfrac{}{}{0ex}{}{n}{s}\right)\le (n/s{)}^s[n/(n-s){]}^{n-s}$ bound the failure probability by ${\sum }_{s=3}^{\lfloor n/2\rfloor }(s/n{)}^s=o(1)$. Split this sum at $\sqrt{n}$. The random k-out graph coupling extends the result to every fixed $k\ge 2$.