Random k-out graph ($G_{k\text{-out}}$)

Each vertex independently chooses $k$ distinct other vertices uniformly, and an undirected edge exists when either endpoint chooses the other. This has dependent undirected edges and is not a binomial random graph. Coupling the choices as the first $k$ entries of independent random permutations makes the graphs increasing in $k$.

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$.