side of is bounded from above by ${\ell_{n}/\delta \choose x\ell_{n}/\delta}$. Using Stirling’s approximation for this term, and substituting in , we get $$\label{eq:probineq}
\begin{aligned}
&\mathbb{P}\left[\exists\, A\subseteq V\colon\,\ell_{A}=x\ell_{n}
\mbox{ and }\left|E\left(A,\overline{A}\right)\right|=y\ell_{n}\right]\\
&\leq \exp\left[\ell_{n}\log\left(x{}^{x\left(1-1/\delta\right)}
\left(1-x\right)^{\left(1-x\right)\left(1-1/\delta\right)}
\left(1-x-y\right)^{-\left(1-x-y\right)/2}\left(x-y\right)^{-\left(x-y\right)/2}y^{-y}\right)\right].
\end{aligned}$$ Recall the definition of $I_{\delta}$ from and note that is exponentially small for $y<I_{\delta}\left(x\right)$, and by a union bound it is exponentially small for all such $y$.

Suppose that after $s$ vertices have been removed, we reach a configuration $\sigma_{s}$ with $\mathcal{H}\left(\sigma_{s}\right) < \mathcal{H}\left(\sigma\right)$, such that for every vertex $v\in\sigma_{s}$ we have $$\left|E\left(v,\sigma_{s}\backslash v\right)\right|+\frac{h}{J}
>\left|E\left(v,\overline{\sigma_{s}}\right)\right|.
\label{eq:afters}$$ In other words, equation (\[eq:afters\]) states that after removing $s$ vertices we are at a configuration of lower energy, and removing any additional vertex leads to a configuration of higher energy. Note that if no such $s$ exists, then we keep on removing vertices until $\boxminus$ has been reached. By the assumption that $h$ is sufficiently small (by , it would suffice if $h<\tfrac12\,
J\,d_\mathrm{ave}\,I_{d_\mathrm{ave}} \left(\tfrac12\right) \frac{n}{\tilde{m}}$, where $\tilde{m}$ was also defined in the aforementioned equation), w.h.p., every configuration $\sigma$ of total degree $\ell_{\sigma}\leq\tfrac12 \ell_n$ satisfies $\mathcal{H}
\left(\sigma\right)>\mathcal{H}\left(\boxminus\right)$. If $v\in\sigma_{s}$ has no self-loops, then we have $$\left|E\left(v,\sigma_{s}\backslash v\right)\right|
=d_{v}-\left|E\left(v,\overline{\sigma_{s}}\right)\right|$$ and thus the condition in is satisfied when for all 