k-Out Graph Sampling

-out graph sampling is a random procedure that selects incident edges locally at each graph vertex of a finite undirected simple graph. In the with-replacement model, each nonisolated graph vertex independently chooses incident edges uniformly with replacement. The sampled spanning subgraph retains all vertices and the union of these choices. An isolated graph vertex chooses nothing. Without replacement, each graph vertex instead chooses a uniformly random -element subset of its incident edges (Holm et al. 2019, Chen and Chen 2026).

For every such graph on vertices and every integer , Chen and Chen (2026) prove that the expected number of original edges joining distinct sampled connected components is . The estimate holds in both models and is sharp up to constants. It fails for . Thus two local choices suffice to leave only original intercomponent edges in expectation. Chen and Chen (2026) report AI assistance in developing and checking parts of the proof.