Lemma 4.5 (Expander Mixing Lemma). Assuming that:

$G$ is $d$ -regular
$G$ is a $(d, 𝜀)$ -expander

Then

\forall S, T \subseteq V

,

| e (S, T) - \frac{d}{n} | S | | T | | \leq \frac{𝜀 d}{n} \sqrt{| S | | T | | S^{c} | | T^{c} |} .