in the ‘Big O’ notation). However in each lemma, the hierarchy is necessary for the fixed parameters in order to guarantee that at least one of the outcomes occurs in the conclusion of the lemma.

Proofs of correctness of algorithms
-----------------------------------

We now give the proofs of the preceding lemmas. We begin with a simple proposition.

\[Claim1\] Let $G$ be an $n$-vertex $D$ regular graph with $D \geq \alpha n$ and let $U$ be a $\rho$-component of $G$. Then

-   $|U| \geq D - \sqrt{\rho}n \geq (\alpha - \sqrt{\rho})n$

-   There are at most $\frac{2\rho}{\alpha(\alpha-\sqrt{\rho})}|U|$ vertices of degree at most $\frac{1}{2}\alpha n$ in $G[U]$.

\(i) Since $G$ is $D$-regular and $U$ is a $\rho$-component, we have $ \frac{1}{2}|U|^2 \geq e_G(U) \geq \frac{1}{2}D |U| - \rho n^2,$ from which we obtain $ |U| \geq D - \frac{\rho n^2}{|U|}\geq D - \sqrt{\rho}n,$ where the second inequality uses that $|U|\geq \sqrt{\rho}n$ since it is a $\rho$-component.

\(ii) If the number of vertices of degree at most $\frac{1}{2} \alpha n$ is $\gamma |U|$, then we have $$(D/2)\gamma|U| + D(1-\gamma)|U| \geq 2e_G(U) \geq D|U|- \rho n^2,$$ from which we get $\gamma \leq \frac{2\rho n^2}{ D |U|} \leq  \frac{2\rho}{\alpha(\alpha-\sqrt{\rho})}$ using part (i) and $D \geq \alpha 