# Regular graphs and eigenvectors

Consider a connected undirected graph $\Gamma$ with an adjacency matrix $A=(a_{ij})_{i,j}$ where $a_{ii}=0$ (and by definition $a_{ij} \in \{0,1\}$ and $a_{ij} = a_{ji}$). Let $\Delta(\Gamma)$ denote the maximum degree of the graph. If an eigenvalue $\lambda = -\Delta(\Gamma)$, we can show for the eigenvector $v=(v_1, \dots ,v_n)^T$ associated with $\lambda$ that $|v_1|=\dots=|v_n|$.

My question is: how do you prove that $\Gamma$ is regular, i.e. that there are the same number of $1$'s in each row/column of the adjacency matrix?

I tried to prove this using $Av=\lambda v$, but this only works for me if $v_1=\dots=v_n$.

• Can you clarify the question? What are you assuming about your graph, and what do you want to prove about it? – Joppy Apr 5 '18 at 12:27
• @Joppy I assume that there is an eigenvalue which is the opposite number of the maximum degree. I need to prove that the graph is regular if such an eigenvalue exists. – Sivlirpa Apr 5 '18 at 12:35

Normalize the eigenvector so that $|v_j|=1, 1\le j\le N.$ For each $j,$ $$\sum_{i=1}^{N}{a_{ij}v_j}=-\Delta(\Gamma)v_j\\ \Delta(\Gamma)=|-\Delta(\Gamma)v_j|=\left\lvert\sum_{i=1}^{N}{a_{ij}v_j}\right\rvert\le\sum_{i=1}^{N}{|a_{ij}|}=\sum_{i=1}^{N}{a_{ij}} \le \Delta(\Gamma),$$ where the last inequality is by definition of \Delta(\Gamma).