Random $k$-out subgraph leaves only $O(n/k)$ inter-component edges

Jacob Holm, Valerie King, Mikkel Thorup +2

Each vertex of an arbitrary simple graph on $n$ vertices chooses $k$ random incident edges. What is the expected number of edges in the original graph that connect different connec…