Two choices suffice: $k$-out sampling leaves $O(n/k)$ intercomponent edges for $k\geq 2$

Introduction

Random edge sampling is a bsimple tool for sparsifying graphs while preserving useful structural information. We study sampling based on local choices at each vertex and ask how many original edges join distinct components of the sample. This property concerns connectivity of the original graph as contracting each sampled component leaves precisely these intercomponent edges and adding them to a spanning forest of the sample preserves the original connected components. Bounds on the number of intercomponent edges are therefore useful for contraction-based minimum-cut algorithms [2], spanning-forest communication protocols [1], and spanning adjacency oracles [13].

Let $G=(V_G, E_G)$ be a simple undirected graph on $n$ vertices. Holm, King, Thorup, Zamir, and Zwick [1] studied this question in the without-replacement $k$-out model, where each vertex $v$ independently chooses a uniformly random subset of $\min\{k,\deg_G(v)\}$ incident edges and the sampled subgraph is the union of these choices. They proved that the expected number of intercomponent edges is $O(n/k)$ for $k\geq \Omega(\log n)$ and conjectured that the same bound should hold for all $k\geq 2$.

We resolve this conjecture in full, for every integer $k\geq 2$, in the stronger with-replacement model. Here each vertex independently samples $k$ incident edges uniformly with replacement, and $H_G^k$ is the union of these choices. Writing $x_G(H)$ for the number of intercomponent edges of a spanning subgraph $H$, we prove the following result.

The bound also holds without replacement as under a natural coupling, the without-replacement subgraph contains $H_G^k$ and has no more intercomponent edges (see § 3.0.0.1). In this work, we use the with-replacement model unless stated otherwise.

The result is optimal in both its sampling rate $k$ and its intercomponent edge count. The bound fails for $k=1$, while examples of Holm, King, Thorup, Zamir, and Zwick [1] have $\Omega(n/k)$ expected intercomponent edges for $2\leq k\leq n/3$, even without replacement.

Technical Contribution and Significance

A key obstacle to extending the analysis of Holm, King, Thorup, Zamir, and Zwick [1] to constant $k$ is their reduction to the expected $k$-out model, where each vertex $v$ independently includes each incident edge with probability $\frac{k}{\max\{k,\deg(v)\}}$. For constant $k$, this model leaves each vertex of a complete graph isolated with constant probability, yielding $\Omega(n^2)$ expected intercomponent edges instead of $O(n)$.

Our analysis bypasses this intermediate model and analyzes the $k$-out model directly using the switching technique. The switching method is a double-counting technique for estimating the relative sizes of classes of combinatorial objects. We define transformations called switchings between the classes and compare the numbers of forward and inverse operations, thereby obtaining counting and probability bounds. In graph applications, a switching typically makes local modifications to the graphs, replacing a small set of edges with another. This is not necessary, but it often makes counting and reasoning about the number of forward and inverse switchings simpler. We use one switching argument to relate intercomponent edges to a component potential, and another to bound the expectation of this potential.

The case $k\geq3$ is outlined in § 2 and proved in § 6. The two-out case in Theorem 12 follows the same two steps but requires more careful treatment.

Implications and Applications

While the distributed sketching application of Holm, King, Thorup, Zamir, and Zwick [1] is already supported by their bound for $k\geq \Omega(\log n)$, extending the bound to constant $k$ enables further algorithmic applications.

In particular, our theorem provides the simplification anticipated by Ghaffari, Nowicki, and Thorup  [2] in their contraction-based algorithms for exact minimum cut in simple unweighted graphs. Their random $2$-out contraction reduces the graph to $O(n/\delta)$ vertices, where $\delta$ is the minimum degree, while preserving any fixed nontrivial minimum cut with constant probability. However, they have no bound on the number of edges that remain, and so they apply an additional sparsification step to reduce the edge count to $O(n)$. Our theorem supplies this edge bound directly for their random $2$-out contraction with replacement, removing the need for the additional edge sparsification step. Combined with their vertex bound, it yields, with constant probability, a contracted instance with $O(n/\delta)$ vertices and $O(n)$ edges that preserves a fixed non-singleton minimum cut. Keeping $k$ constant is essential here, since it is what gives the constant cut-survival probability.

The same contraction principle improves exact minimum cut in the cut-query model, where each query returns the number of edges crossing a specified vertex subset. Kenneth-Mordoch and Krauthgamer  [6] obtained a two-round algorithm using $\widetilde O(n^{4/3})$ queries by constructing a contraction in the first round and recovering the contracted graph in the second. The recovery cost is nearly linear in the number of remaining vertices and edges. Our expected edge bound lets these sampling and recovery primitives implement random $2$-out contraction and reconstruct the contracted graph using $\widetilde O(n)$ queries, with the cut-survival guarantee above.

Related Work

Early work focused on $k$-out sampling in the complete graph. Fenner and Frieze  [17] established $k$-vertex and $k$-edge connectivity for $k\geq 2$, Frieze  [20] proved the existence of perfect matchings for even-order graphs when $k\geq 2$, and Bohman and Frieze  [18] proved Hamiltonicity for $k\geq 3$, all with probability tending to $1$. These results can be found in the book by Frieze and Karoński  [21].

Frieze and Johansson  [19] extended connectivity and Hamiltonicity results to graphs $G$ whose minimum degree is $(1/2+\epsilon)n$ for some $\epsilon>0$. They showed that $H^k_G$ is $k$-connected w.h.p. for $k = O(1)$ and is Hamiltonian for sufficiently large $k$. However, they remarked that such results are not possible for graphs with smaller minimum degree.

Minimum cut.

Beyond the cut-query application above, random $2$-out contraction has also been used in streaming. Assadi and Dudeja [12] gave a two-pass algorithm for exact global minimum cut using $O(n\log n)$ bits of space, whose first pass builds a with-replacement $2$-out sample.

Spanning structures.

The bound of Holm, King, Thorup, Zamir, and Zwick [1] also gives a one-way communication protocol for finding a spanning forest, using private randomness and $O(\sqrt{n}\log n)$ bits per vertex. Bodwin and Fleischmann [13] also apply this bound to spanning adjacency oracles, which implicitly represent a sparse spanning subgraph and answer edge-membership queries. One construction uses $k$-out sampling.

Beyond connectivity.

Saneian and Behnezhad [16] use one-sided random $3$-out sampling in bipartite graphs for streaming edge coloring. Each vertex on one side independently chooses three distinct uniform neighbors on the other. When the opposite side is larger by a sufficiently large constant factor, the sample contains a matching covering the sampling side with high probability.

Implementations.

The ConnectIt framework of Dhulipala, Hong, and Shun [14] and the GPU study of Hong, Dhulipala, and Shun [15] evaluate $k$-out sampling and its variants for parallel connectivity.

The switching method.

As described in Wormald’s survey [3], McKay introduced switchings into the study of random graphs to bound subgraph probabilities in random graphs with prescribed degrees  [10]. Since then, the switching argument has found many applications, including cycle counts and girth  [7], connectivity  [8], asymptotic estimates of spanning trees  [9], and asymptotic enumeration of graphs with prescribed degrees  [11]. Switchings are also crucial in the analysis of exact uniform generation algorithms, beginning with the work of McKay and Wormald [4] which was later improved by Arman, Gao, and Wormald [5] also using switching.

Technical Overview

We prove the bound by relating intercomponent edges to a degree-sensitive potential of the sampled components, and then showing that a special augmentation of a $2$-out sample has expected potential $O(n)$.

From intercomponent edges to component potential

We first describe a simple switching argument to demonstrate how it can be useful. Fix $r<k$, and leave the first $r$ choices at every vertex unchanged. For each intercomponent edge $e$ of $H^k$, choose its smaller-degree endpoint $v$ and replace any one of its remaining $k-r$ choices by $e$. Each replacement makes $e$ a bridge of the new sample outside the unchanged $H^r$.

Each intercomponent edge therefore gives $k-r$ forward switchings. Conversely, an image bridge at $v$ admits at most $\deg_G(v)$ inverse switchings, one for each possible previous choice. Thus forward switchings count intercomponent edges multiplied by $k-r$, while inverse switchings are bounded by bridges weighted by the smaller degree of their endpoints.

These bridge weights are controlled by the component potential

Indeed, after contracting the components of $H^r$, the bridges outside $H^r$ form a forest. Rooting its trees and charging each bridge to its child component results in at most one charge per component. Each charge is at most that component’s maximum original degree. Double-counting the switchings therefore gives

It remains to bound the expected potential of a suitable subgraph by $O(n)$.

Bounding the component potential

Fix a total order on the vertices by nondecreasing degree, breaking ties arbitrarily. Call the largest vertex of each component its leader, and order the components by their leaders. The potential $\Phi_G(H)$ is the sum of the leaders’ degrees. Their internal neighbors contribute at most $n$ because the components are disjoint, so it remains to control their crossing edges. Consider each crossing edge to be owned by the endpoint in the higher component. We prove a bound on the crossing edges owned by leaders using a recurrence.

A recurrence for edges at successive depths.

Write $x_G^j(H^2)$ for the number of crossing edges whose owner is at distance $j$ from its leader. For such an edge $uv$ with owner $u$, replace either choice at $v$ in the lower component by $uv$. The inserted edge becomes a bridge, and $v$ is now at depth $j+1$ from the higher leader. We establish

The factor of two comes from the two choices that can be replaced at $v$. To reverse a switch, fix an image and recover the previous choice at $v$. A valid previous choice either stays inside the branch separated from the leader by the inserted bridge $uv$, or leads to another lower component. In the first case, the branches below bridges at the same depth are disjoint and therefore sum up to $n$. In the second case, the previous edge is a crossing edge in the image owned by $v$ at depth $j+1$, counted by $x_G^{j+1}(H^2)$. Solving the recurrence gives

Using one additional choice.

It remains to handle leaders’ edges to higher components. A leader with many such edges is likely to select one of them given an additional choice, allowing us to merge its component into a higher one and remove its degree from the potential.

This motivates the augmentation $H^{2+}$. Add each $H^2$-leader’s third choice only when it reaches a higher $H^2$-component. Conditioned on $H^2$, a leader survives as a leader in $H^{2+}$ with probability equal to the fraction of its neighbors lying inside its own component or in lower components. Since each surviving leader contributes its degree to the potential, multiplying the surviving probability by its degree gives the expected contribution to the potential, which is exactly the number of these neighbors. Summing the internal neighbors and crossing edges to lower components gives

Refining the Switching Argument for $k\geq 3$

Since $H^{2+}\subseteq H^3$, the same potential bound holds for $H^3$. Taking $r=3$ in the first switching argument gives the desired bound for $k\geq4$. To reach $k=3$, we must protect fewer edges, leaving room for switching. We refine the switch so that the inserted crossing edge is a bridge outside $H^{2+}$ in the image, giving

The refined switching argument is given in § 6.

Preliminary

Let $G=(V_G, E_G)$ be a simple graph, and let $N_G(v)$ denote the neighbors of $v$ in $G$. We may assume that $G$ has no isolated vertices, as deleting them does not change the intercomponent edges and only decreases $n$. Define the $k$-out sampling process as each node $v\in V_G$ independently and uniformly sampling $k$ edges with replacement. The random $k$-out subgraph $H_G^{k}$ is formed by taking the union of these sampled edges. These subgraphs admit a natural coupling. Consider the process in which each vertex independently generates an infinite sequence of independent, uniformly random incident edges

The union of the first $k$ choices at each vertex gives $H_G^k(\sigma)$, where $\sigma:=\{\sigma_v\}_{v\in V_G}$. Thus,

For fixed $k$, the ordered outcomes consisting of the first $k$ choices, including repetitions, all have probability $\prod_{v} \deg_G(v)^{-k}$. Our counting arguments use these finite prefixes as outcome, and containment is defined by prefixes. Outcome $H^k(\sigma)$ contains outcome $H^j(\sigma')$ if $\sigma'_v$ restricted to the first $j$ positions is a prefix of $\sigma_v$ for all $v\in V_G$.

Let $\mathcal{CC}(G)$ be the set of connected components of $G$ and $\mathrm{cc}(G)=|\mathcal{CC}(G)|$. For a spanning subgraph $H=(V_G,E_H)\subseteq G$, define its intercomponent edges by

We also call these edges crossing and write $x_G(H)=|X_G(H)|$. We omit the subscript $G$ when it is clear from context.

Comparison of the sampling models.

Let $H^k_{\mathrm{wr}}$ and $H^k_{\mathrm{wor}}$ denote the random $k$-out subgraphs obtained with and without replacement, respectively. Using the sequences $\sigma_v$ above, take the first $k$ draws for $H^k_{\mathrm{wr}}$ and the first $\min\{k,d_G(v)\}$ distinct edges for $H^k_{\mathrm{wor}}$. All incident edges appear almost surely (with probability $1$) in the infinite sequence, and their order of first appearance is a uniformly random permutation, so both marginals have the required distributions. Every edge among the first $k$ draws belongs to the without-replacement sample. Hence,

Since having more edges can only merge components and reduce crossing edges, we have

Hence, applying Theorem 1, we have $\mathop{\mathrm{\mathbb{E}}}[x_G(H^k_{\mathrm{wor}})] \leq \mathop{\mathrm{\mathbb{E}}}[x_G(H^k_{\mathrm{wr}})] \leq O(n/k)$, for all $k\geq 2$.

Bridge Potential to Component Potential

We define two potentials for spanning subgraphs of $G$ that are important in our main arguments.

Bridge Potential

An edge is a bridge if deleting it increases the number of connected components. Let $\operatorname{Br}(G)$ denote the bridges of $G$. For nested spanning subgraphs $J\subseteq H\subseteq G$, define the bridge potential by

Each bridge’s weight is at most either endpoint’s degree. We can therefore charge it to either endpoint’s component, using that component’s maximum $G$-degree.

Max-degree Component Potential

For any spanning subgraph $J=(V_G, E_J)$ of $G$, define its max-degree component potential $\Phi$ by

which charges each component of $J$ the largest degree of its vertices, with all degrees measured in the original graph $G$. Merging components can only decrease $\Phi_G$. Hence, if $J\subseteq H$, $\Phi_G(H)\leq \Phi_G(J)$. The following lemma relates the two potentials.

Warm-up: Switching Lemma and the near-regular case

In this section, we demonstrate how to reduce the problem of bounding intercomponent edges to bounding the sum of the maximum degrees of each component via a key technique we call the switching argument. We prove the following lemma in this section.

By applying the following lemma on the number of components of $2$-out subgraphs due to Ghaffari, Nowicki, and Thorup [2], we can get a simple corollary bounding the number of intercomponent edges in nearly regular graphs.

The above corollary can be extended to $k \geq 2$ by extending the switching argument to real numbers $r$, by selecting the final choice with probability $r-\lfloor r\rfloor$, and complementing it with a generalization of Lemma 4 to random subgraphs that select the second edge with non-zero probability. However, for simplicity of warm-up, we will not expand on the details.

Motivated by applications, we now move on to the proof of Lemma 3, where we use our key technique, the switching argument, a form of careful double counting.

[proof picture,x=1cm,y=1cm]
  \node[proof heading] at (3.5,2.15) {(a) Source $\sigma$: $e$ is crossing};
  \node[proof heading] at (11.35,2.15) {(b) Image $\sigma'$: $e$ is a bridge};
  \begin{scope}
    \draw[proof region] (0,-.9) rectangle (2.65,1.65);
    \draw[proof region] (4.35,-.9) rectangle (7,1.65);
    \node[proof vertex] (v) at (2,.2) {$v_e$};
    \node[proof vertex] (w) at (.65,-.25) {$w$};
    \node[proof dot] (a) at (.85,1) {};
    \node[proof vertex] (u) at (4.95,.2) {$u$};
    \node[proof dot] (b) at (6.25,1) {};
    \node[proof dot] (c) at (6.25,-.3) {};
    \draw[proof edge] (v)--(a)--(w) (u)--(b)--(c)--(u);
    \draw[proof choice] (v)--node[below,proof tag] {$f$}(w);
    \draw[proof crossing] (v)--node[above,proof tag] {$e$}(u);
    \node[proof note] at (3.5,-1.35)
      {switch at the smaller-degree endpoint $v_e$};
  \end{scope}
  \begin{scope}[xshift=7.85cm]
    \draw[proof region] (0,-.9) rectangle (7,1.65);
    \node[proof vertex] (v2) at (2,.2) {$v_e$};
    \node[proof vertex] (w2) at (.65,-.25) {$w$};
    \node[proof dot] (a2) at (.85,1) {};
    \node[proof vertex] (u2) at (4.95,.2) {$u$};
    \node[proof dot] (b2) at (6.25,1) {};
    \node[proof dot] (c2) at (6.25,-.3) {};
    \draw[proof edge] (v2)--(a2)--(w2) (u2)--(b2)--(c2)--(u2);
    \draw[proof removed] (v2)--node[below,proof tag] {$f$}(w2);
    \draw[proof bridge] (v2)--node[above,proof tag] {$e$}(u2);
    \node[proof note] at (3.5,-1.35)
      {one selecting position; $e\notin H^r$};
  \end{scope}

Bounding the Component Potential and the Consequence for $k\geq 4$

In § 4, we show how the switching argument relates the number of crossing edges $x_G(H^k)$ to the max-degree component potential $\Phi_G(H^r)$. In this section, we prove the $k$-out conjecture for every $k\ge 4$ by providing a linear bound on $\mathop{\mathrm{\mathbb{E}}}[\Phi(H^{3})]$ improving on the crude bound $\Delta\cdot\mathrm{cc}(H)$.

Fix an order on the vertices by increasing degrees in $G$, breaking ties arbitrarily. We call the largest vertex of a component, which is also the one with the largest original degree, its leader. Denote $\alpha_C$ as the leader of a component $C$. Then the component potential $\Phi_G(H)$ is the sum of the degrees of the leaders of each connected component. That is

We call a component higher if its leader is higher and lower if its leader is lower.

Augmented $2$-out Graph

To show a potential bound, our idea is to utilize an additional choice at some of the vertices to merge components together, effectively removing one previous leader from the sum toward the potential. With this idea in mind, we define the augmented $2$-out graph $H^{2+}$ in the following way. First, we sample $H^2$. Then for the leader of each connected component in $H^2$, we sample a third choice. If this edge connects to another component with a higher leader, we add that edge to $H^{2+}$. The sampling coupling applies. For the same sequence $\sigma$,

With this lemma, we can show our desired bound for $k\geq 4$ quite simply.

Proof of Lemma 6: Bounded Potential on Augmented $2$-out graph

The graph $H^{2+}$ is built upon $H^2$ by adding a third randomly sampled edge from a leader of $H^2$ if that edge connects to a higher component. Hence, if a leader of $H^2$ fails to merge to a higher component, it remains a leader of $H^{2+}$ and contributes to both $\Phi(H^{2+})$ and $\Phi(H^2)$. On the other hand, if a leader of $H^2$ merges with a higher component due to its third choice, it contributes $0$ to $\Phi(H^{2+})$. The leaders of $H^{2+}$ is a subset the leaders of $H^2$, so no other vertices can contribute to $\Phi(H^{2+})$.

Conditioned on the first two choices of the sequences at each vertex, we can calculate the expected contribution of the leaders in $H^2$ to $\Phi(H^{2+})$ by bounding the probability of them staying as a leader.

Suppose $\alpha_C$ is the leader for a connected component $C$ in $H^2$. Let $d_C\leq \deg_G(\alpha_C)$ denote the number of bad neighbors of $\alpha_C$ whose connection fails to merge $C$ into a higher component. This includes exactly neighbors inside $C$ and neighbors in lower components. The probability that $\alpha_C$ remains a leader in $H^{2+}$ is

If $\alpha_C$ remains a leader, it contributes $\deg_G(\alpha_C)$ to $\Phi(H^{2+})$. Hence, its expected contribution in this case is $\deg_G(\alpha_C) \cdot \frac{d_C}{\deg_G(\alpha_C)}= d_C$. Hence,

Therefore, it is sufficient to show that the sum of the bad neighbors of the leaders in $H^2$ is small. For each leader $\alpha_C$, we decompose the bad neighbors into internal neighbors in $C$, $N_G(\alpha_C)\cap C$, and external neighbors connecting to lower components in $H^2$, denoted by $d_C^\downarrow$. Since the components are disjoint, $\sum_{C\in \mathcal{CC}(H^2)} |N_G(\alpha_C)\cap C|\leq \sum_{C\in \mathcal{CC}(H^2)} |C| \leq n$. Then, we can write

where $L_G(H) := \sum_{C\in \mathcal{CC}(H)} d_C^\downarrow$ is the sum of the leaders’ external neighbors in lower components. Bounding the expectation of $L_G(H)$ allows us to bound the expected potential of $H^{2+}$.

Leaders’ external neighbors in lower components

Now we bound $L(H^2)$, the total number of external neighbors in lower components for leaders in $H^2$. We consider all crossing edges to be owned by the endpoint in the higher component. Fix a spanning subgraph $H$ of $G$, for each vertex $v$, define the depth of $v$ in $H$ as its distance to the leader of its component. For any subgraph $H$ of $G$, define $x^j_G(H)$ as the number of crossing edges whose owner is at depth $j$ of its component. Note that $x^0_G(H) = L_G(H)$. We will show the following relationship between the expected number of crossing edges at adjacent depths via a version of switching argument.

[proof picture,x=1cm,y=1cm]
  \node[proof heading] at (3.45,3.3) {(a) Forward: switch at the lower endpoint};
  \node[proof heading] at (11.25,3.3) {(b) Image: the two inverse cases};
  \begin{scope}
    \draw[proof region] (0,-.35) rectangle (2.25,2.8);
    \draw[proof lower] (4,-.35) rectangle (6.9,2.8);
    \node[proof leader] (a) at (1.1,2.1) {$\alpha_C$};
    \node[proof vertex] (u) at (1.1,.55) {$u$};
    \node[proof vertex] (v) at (4.6,.55) {$v$};
    \node[proof vertex] (w) at (6.2,1.9) {$w$};
    \node[proof dot] (t) at (6.2,.2) {};
    \draw[proof path] (a)--node[right,proof note] {$j$}(u);
    \draw[proof edge] (v)--(t)--(w);
    \draw[proof choice] (v)--node[left,proof tag] {$vw$}(w);
    \draw[proof crossing] (u)--node[above,proof tag] {$uv$}(v);
    \node[proof note] at (1.1,-.75) {higher component};
    \node[proof note] at (5.45,-.75) {lower component};
    \node[proof note,text width=6.9cm] at (3.45,-1.45)
      {Replace either retained choice at the lower endpoint $v$.};
  \end{scope}
  \begin{scope}[xshift=7.8cm]
    \draw[proof region] (0,1) rectangle (6.9,2.8);
    \draw[proof child] (3.65,1.1) rectangle (6.8,2.7);
    \draw[proof lower] (3.65,-1) rectangle (6.8,.45);
    \node[proof leader] (a2) at (.65,2) {$\alpha_C$};
    \node[proof vertex] (u2) at (2.25,2) {$u$};
    \node[proof vertex] (v2) at (4.25,2) {$v$};
    \node[proof vertex] (w2) at (6.05,2) {$w_{\rm in}$};
    \node[proof vertex] (z2) at (6.15,-.3) {$w_{\rm out}$};
    \draw[proof path] (a2)--node[above,proof note] {$j$}(u2);
    \draw[proof bridge] (v2)--node[above,proof tag] {$uv$}(u2);
    \draw[proof path] (v2) to[bend left=30] (w2);
    \draw[proof removed] (v2)--(w2);
    \draw[proof crossing] (v2) -- (4.25,.7)
      -- node[below,proof tag] {$vw$} (6.15,.7) -- (z2);
    \node[proof note] at (5.6,1.35) {child side $C_v$};
    \node[proof note,anchor=west,text width=1.7cm] at (3.75,-.3) {lower\\component};
    \node[proof note] at (4.25,2.5) {$j+1$};
    \node[proof note,text width=6.9cm] at (3.45,-1.65)
      {Restore $vw$ either inside $C_v$, or to a lower component.
       In the second case, $v$ owns the residual edge.};
  \end{scope}

With all ingredients needed, we can finally prove Lemma 6.

Refined Switching to the Augmented $2$-out Graph and the $k\geq 3$ case

In this section, we will prove a lemma analogous to Lemma 3. If we can relate the crossing edge of $H^k$ to the augmented $2$-out graph $H^{2+}$, then applying Lemma 6, we can arrive at the following version of Theorem 1 for $k\geq 3$.

[proof picture,x=1cm,y=1cm]
  \node[proof heading] at (3.5,3) {(a) Before: $v_e$ leads an $H^2$-component};
  \node[proof heading] at (11.35,3) {(b) After: $v_e$ is no longer a leader};
  \begin{scope}
    \draw[proof region] (0,-1.6) rectangle (3.05,2.5);
    \draw[proof child] (4.55,.65) rectangle (7,2.5);
    \draw[proof lower] (4.55,-1.6) rectangle (7,.05);
    \node[proof leader] (v) at (2.3,.55) {$v_e$};
    \node[proof vertex] (w) at (.65,1.65) {$w$};
    \node[proof dot] (t) at (.65,-.65) {};
    \node[proof leader] (a) at (5.8,1.6) {$\alpha_D$};
    \node[proof vertex] (u) at (5.8,-.75) {$u$};
    \draw[proof edge] (w)--(t);
    \draw[proof choice] (v)--node[above left,proof tag] {$f_1$}(w);
    \draw[proof edge] (v)--node[below left,proof tag] {$f_2$}(t);
    \draw[proof bridge] (v)--node[above,sloped,proof tag] {$f_3$}(a);
    \draw[proof crossing] (v)--node[below,sloped,proof tag] {$e$}(u);
    \node[proof note] at (5.8,1) {$\alpha_D>v_e$};
    \node[proof note] at (1.5,-1.25) {$H^2$-component};
    \node[proof note,text width=7cm] at (3.5,-2.15)
      {$f_3$ already joins a higher component in $H^{2+}$;
       $e$ crosses the full $H^k$-components.};
  \end{scope}
  \begin{scope}[xshift=7.85cm]
    \draw[proof region] (0,-1.6) -- (3.05,-1.6) -- (3.05,.65)
      -- (7,.65) -- (7,2.5) -- (0,2.5) -- cycle;
    \draw[proof lower] (4.55,-1.6) rectangle (7,.05);
    \node[proof vertex] (v2) at (2.3,.55) {$v_e$};
    \node[proof vertex] (w2) at (.65,1.65) {$w$};
    \node[proof dot] (t2) at (.65,-.65) {};
    \node[proof leader] (a2) at (5.8,1.6) {$\alpha_D$};
    \node[proof vertex] (u2) at (5.8,-.75) {$u$};
    \draw[proof edge] (w2)--(t2);
    \draw[proof removed] (v2)--node[above left,proof tag] {$f_1$}(w2);
    \draw[proof edge] (v2)--node[below left,proof tag] {$f_2$}(t2);
    \draw[proof bridge] (v2)--node[above,sloped,proof tag] {$f_3$: first}(a2);
    \draw[proof choice] (v2)--node[below,sloped,proof tag] {$e$: third}(u2);
    \node[proof note] at (1.55,-1.25) {new $H^2$-component};
    \node[proof note,text width=7cm] at (3.5,-2.15)
      {$f_3$ connects $v_e$ to a higher leader already in $H^2$;
       its third choice $e$ is not added to $H^{2+}$.};
  \end{scope}

Now we can prove Theorem 10.

The $2$-out case

In this section, we extend the result to $2$ choices with replacement. We follow the same two steps as before: relate intercomponent edges to a component potential, and then bound the expected potential. For simplicity of presentation, we only show the argument for the $2$-out case. For $k\geq3$, one can either use Theorem 10 to get the desired bound with a better constant or extend the following argument to fit general $k$. The constants below are chosen to simplify the proof.

Technical overview

The $3$-out argument protects two choices and some third choices to make the potential small, leaving the other third choices available for switching. With only two choices, these two uses compete for the same second choice. Our idea is to restrict the switching argument to a constant fraction of the crossing edges in expectation. This loses only a constant factor in the reduction, but leads to a weaker potential in which each leader contributes only its relevant degree which counts only the neighbors used in switching.

Since we only need to switch from a random subset of vertices, we can protect two choices at the other vertices. The graph whose potential we need to bound is therefore an augmented $1$-out graph that is already close to a $2$-out graph. We can then adapt the earlier potential argument to bound this weaker potential in expectation by $O(n)$.

Some technical details that are different from the $3$-out case are as follows. We use a random proper coloring to define the vertices and edges that can perform switchings. As the result, we are no longer working with uniform distributions on the source and image. Hence, we need to correct the expectation calculation with the ratio of the probabilities.

Preliminary

Recall that for the $2$-out graph, each vertex $v$ independently samples two incident edges ${\sigma}_v=(e_{v,1},e_{v,2})$ uniformly at random, with replacement. Write $s_{i}(v)$ for the other endpoint of the $i$-th selected edge $e_{v,i}$.

The marked set and the base graph.

Conditional on ${H_{G}^{1}}(\sigma)$, choose a uniformly random proper coloring with colors $0,1,\ldots,9$. Let $S$ be its zero set, call its vertices marked, and put $U=V_G\setminus S$. The set $S$ is an independent set in ${H_{G}^{1}}(\sigma)$. Uniform randomness on coloring is crucial in our analysis, since this gives each vertex probability $1/10$ of being marked and provides the probability estimates needed after switching. An arbitrary proper coloring need not satisfy these estimates. The choice of ten is arbitrary, and any constant larger than 3 would suffice. We only need the information about the $S$, so an outcome is the pair $({\sigma},S)$.

We consider the base graph ${B}({\sigma},S)$ that keeps the first position at every vertex and the second position of every vertex in $U$. Thus, all second choices at $S$ are omitted from ${B}$. Among these omitted second choices, we reserve those leaving $S$ for possible use in the augmentation. Denote the set of vertices with reserved choices by