\alpha) (\alpha \nu n'/2) \leq \nu n'^2.$$

Set $U':=U\setminus U_0$ and choose $\phi$ such that $\nu\ll \phi \ll \rho'$. We apply Theorem \[th:cheeger\] to $G[U']$ as follows to construct $U_1, U_2, \ldots$. Given $U_i$, set $\overline{U_i}:=U\setminus U_i$ and $G_i:= G[\overline{U_i}]$ apply the algorithm of Theorem \[th:cheeger\] to $G_i$ to output some $S_i \subseteq \overline{U_i}$. By replacing $S_i$ with $U_i \setminus S_i$ if necessary, assume $|S_i| \leq |U_i \setminus S_i|$. If

1.  $\phi_i := \Phi_{G_i}(S_i)> \phi$ or $|U_i|\geq \frac{1}{3}|U|$

then stop. Otherwise set $U_{i+1}=U_i \cup S_i $ and repeat. In this way we obtain sets $S_0, \ldots, S_{t-1}$ and $U_0, \ldots, U_t$ in polynomial time. Note that $|U_{t-1}| < \frac{1}{3} |U|$, so $$\label{eq:Ut}
     |U_t| = |U_{t-1}|+|S_{t-1}| \leq |U_{t-1}| + \frac{1}{2} (|U| -|U_{t-1}|)  \leq \frac{2}{3} |U|.$$ There are two cases to consider:

1.  $|U_t| > \frac{1}{4} \rho'n'$ and

2.  $|U_t| \leq \frac{1}{4} \rho'n'$.

\[Claim3\] In case (a), $U_t$, $\overline{U_t}$ are $\rho'$-components.

\[Claim4\] In case (b), $G[U]$ is a robust $(\nu, \tau)$-expander.

Since we can output $U_t,\overline{U_t}$ in polynomial time, these two claims prove Lemma \[th:alg1\].

Since we are in case (a), note that $\Phi_{G_i}(S_i) \leq \phi$ for all $i=1, \ldots, t$ and so $$\label{eq:vol2}
e_G(S_i, U_i \setminus S_i) \leq \phi {\text{vol}}_{G_i}(S_i) \leq 