Past exam of the mathematics course of the University of Cambridge / 2005 / iii / Paper 12 / 3

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 exactlyFor $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 $\left(\genfrac{}{}{0ex}{}{n}{s}\right)\le t^{-s}(1-t{)}^{-(n-s)}$ follows by bounding the probability of $s$ successes in $\mathrm{Bin}(n,t)$ by one. Thus the union bound givesFor $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. ThereforeThe proof bounds all possible small components rather than assuming the dependent undirected edges behave like a binomial random graph.

At each vertex independently, take a uniformly random permutation of the other $n-1$ vertices. Use its first two entries for the two-out choices and its first $k$ entries for the $k$-out choices. Every unordered choice set has the prescribed uniform distribution, and choices at different vertices remain independent. This couples the random k-out graphs so that $G_{2\text{-out}}\subseteq G_{k\text{-out}}$ on the same vertex set. Adding edges cannot destroy graph connectivity. ConsequentlyThis establishes connectivity of random k-out graphs for every fixed allowed $k$.