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

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