Lemma 4.18. The eigenvalues of $Ĝ$ are the eigenvalues of $A_G$ (old) together with the eigenvalues of $S$ (new).