Choose a set \(X\) of \(\alpha n\) \(c\)-regular vertices uniformly at random. Consider a fixed \(d\)-regular vertex; each of its \(d\) neighbours lies in \(X\) with probability \(\alpha \), so the probability it is not a neighbour of \(X\) is

which tends to \((1-\alpha )^d\) as \(n\to \infty \). Hence the expected number of \(d\)-regular non-neighbours tends to \(\frac{c}{d}n(1-\alpha )^d\), so the expected number of neighbours is \(\frac{c}{d}n\bigl(1-(1-\alpha )^d\bigr)+O(1)\). Some choice of \(X\) achieves at most the expectation, giving the bound. The bound becomes tight as \(c\) grows.

Fix a set \(V\) of \(\alpha n\) variables. The probability that a given constraint is a neighbour of \(V\) is at least \(1-(1-\alpha )^d\), so the expected number of neighbours of \(V\) is at least \(n\frac{c}{d}\bigl(1-(1-\alpha )^d\bigr)\).

Each of the \(c\alpha n\) edges leaving \(V\) has its endpoint revealed one at a time. Let \(X_i\) be the expected size of the neighbour set of \(V\) given that the first \(i\) edges leaving \(V\) have been revealed. Then \(X_0,\dots ,X_{c\alpha n}\) is a martingale with \(|X_{i+1}-X_i|\le 1\), \(X_0\) is the expectation above, and \(X_{c\alpha n}\) is the actual number of neighbours. By Azuma’s inequality (Lemma 5),

There are only \(\binom {n}{\alpha n}\) choices of \(V\), so it suffices to choose \(\lambda \) with \(\binom {n}{\alpha n}e^{-\lambda ^2/2}\ll 1\). By Stirling’s formula \(\binom {n}{\alpha n}\le 2^{nH(\alpha )}\), so the condition holds for large \(n\) once \(\frac{nH(\alpha )}{\log _2 e}{\lt}\frac{\lambda ^2}{2}\), i.e. \(\lambda {\gt} \sqrt{2nH(\alpha )/\log _2 e}\). Substituting this \(\lambda \) into the deviation \(\lambda \sqrt{c\alpha n}\) and dividing by \(n\) gives the stated shortfall \(\sqrt{2c\alpha H(\alpha )/\log _2 e}\) below the expectation, uniformly over all \(V\) with exponentially high probability.