Given a simple undirected graph on $n$ vertices, $k$-out sampling lets each vertex independently pick $k$ incident edges uniformly (with replacement), producing a spanning subgraph. We show that for every integer $k\ge2$ the expected number of original edges that connect distinct sampled components is $O\left(\frac{n}{k}\right)$. This fully resolves the conjecture of Holm, King, Thorup, Zamir, and Zwick, improving the previously required $\Theta(\log n)$ sampling to the optimal threshold of two local choices per vertex. The bound fails when $k=1$, and the $O(n/k)$ dependence is tight up to constant factors. Because the sampling allows replacement, the result also holds without replacement. Consequently, contracting just two independent local choices per vertex suffices in expectation to reduce any simple graph to a quotient with $O(n)$ edges, a key step for many contraction‑based algorithms. The proof relies on switching arguments: first relating inter‑component edges to bridges, then introducing a degree‑weighted component potential and bounding its expectation again via a switching argument.
Review