= 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. Consequently
$$
\boxed{\Pr(G_{k\text{-out}}\text{ connected})\ge\Pr(G_{2\text{-out}}\text{ connected})\longrightarrow1\quad(k\ge2).}
$$
This establishes <connectivity of random k-out graphs> for every fixed allowed $k$.
Back to article page
