5. Regular Graphs

It is clear that $\bar{k}=n-k-1$. Let $v_i$ and $v_j$ be two adjacent vertices in $G$, and thus $v_j$ and $v_j$ are non-adjacent in $\bar{G}$. In $G$, let ${\mathrm{\Omega }}_i$ be the vertices adjacent to $v_i$ that are not adjacent to $v_j$ and let ${\mathrm{\Omega }}_j$ be the vertices adjacent to $v_j$ that are not adjacent to $v_i$, and let ${\mathrm{\Gamma }}_{i,j}$ be the set of vertices not adjacent to neither $v_i$ nor $v_j$. Therefore, in $\bar{G}$ the non-adjacent vertices $v_i$ and $v_j$ have $|{\mathrm{\Gamma }}_{i,j}|$ common neighbors. Since $|{\mathrm{\Omega }}_i|=|{\mathrm{\Omega }}_j|=k-s-1$ and ${\mathrm{\Omega }}_i\cap {\mathrm{\Omega }}_j=\mathrm{\varnothing }$ we have $$n=|{\mathrm{\Gamma }}_{i,j}|+|{\mathrm{\Omega }}_i|+|{\mathrm{\Omega }}_j|+s+2$$ from which it follows that $|{\mathrm{\Gamma }}_{i,j}|=n-2k+s$. Hence, in $\bar{G}$, any non-adjacent vertices have $\bar{t}=n-2k+s$ common neighbors. The formula for $\bar{s}$ is left as an exercise (Exercise 5.1).

The $(i,j)$ entry of ${\mathbf{A}}^2$ is the number of walks of length 2 from $v_i$ to $v_j$. If $v_i$ and $v_j$ are adjacent then they have $s$ common neighbors and each such neighbor determines a walk from $v_i$ to $v_j$ of length 2. On the other hand, if $v_i$ and $v_j$ are non-adjacent then they have $t$ common neighbors and each such neighbor determines a walk from $v_i$ to $v_j$ of length 2. If $v_i=v_j$ then the number of walks from $v_i$ to $v_j$ is $k$. Hence, $$({\mathbf{A}}^2{)}_{i,j}=\{\begin{array}{ll}s,& v_i{v}_j\in E(G)\\ t,& v_i{v}_j\notin E(G)\\ k,& i=j\end{array}$$ This yields the desired formula for ${\mathbf{A}}^2$.

Let $\mathbf{z}$ be an eigenvector of $\mathbf{A}$ corresponding to an eigenvalue $\lambda$ not equal to $k$. Then $\mathbf{z}$ is orthogonal to the all ones vector and thus $\mathbf{J}\mathbf{z}=\mathbf{0}$. Then from $\text{(???)}$ we have ${\mathbf{A}}^2-(s-t)\mathbf{A}-(k-t)\mathbf{I}=t\mathbf{J}$ and therefore $$({\lambda }^2-(s-t)\lambda -(k-t))\mathbf{z}=0$$ and therefore ${\lambda }^2-(s-t)\lambda -(k-t)=0$. The roots of the polynomial $x^2-(s-t)x-(k-t)=0$ are precisely $\alpha$ and $\beta$. Since $\text{tr}(\mathbf{A})$ is the sum of the eigenvalues of $\mathbf{A}$, $\text{tr}(\mathbf{A})=0$, and $k$ has multiplicity one, we have $m_{\alpha }+m_{\beta }=n-1$ and $\alpha m_{\alpha }+\beta m_{\beta }+k=0$. Solving these equations for $m_{\alpha }$ and $m_{\beta }$ yield $m_{\alpha }=-\frac{(n-1)\beta +k}{\alpha -\beta }$ and $m_{\beta }=\frac{(n-1)\alpha +k}{\alpha -\beta }$, and substituting the expression for $\alpha$ and $\beta$ yield stated expressions.