# A finite graph G is $d$-regular if, and only if, its adjacency matrix has the eigenvalue $λ = d$

Show that a graph $G$ ﬁnite with $n$ vertices is $d$-regular if, and only if, the vector with all the coordinates equals to 1 is eigenvetor from eigenvalue $λ = d$ from the adjacency matrix $A$ from the graph $G$. The question itself was a little confused for me...

-

Funny thing, I just learned this myself this week. It is proposition 3 on page 2 of these excellent lecture notes by Padraic Bartlett. The entire set of lecture notes on spectral graph theory is here.

(I promised in 2012 to write up the proof here, but I hereby retract that promise. I would not be able to improve upon Brian Scott's writeup elsewhere in this thread.)

-
Thank you so much!!!! – HipsterMathematician May 28 '12 at 2:31
Today was my test...this question was in it.... – HipsterMathematician May 29 '12 at 21:00
@MarylinM.J I hope you passed! – MJD May 29 '12 at 22:01
@ Mark Dominus I took Ten!!!! – HipsterMathematician Jun 9 '12 at 20:43
@HipsterMathematician Congratulations! – MJD Jan 23 '15 at 22:31

Suppose that $G$ is $d$-regular. Then every vertex of $G$ is adjacent to $d$ other vertices, so each row of its adjacency matrix $A$ will have $d$ $1$’s and $n-d$ $0$’s. Let

$$A=\pmatrix{a_{11}&a_{12}&\dots&a_{1n}\\ a_{21}&a_{22}&\dots&a_{2n}\\ \vdots&\vdots&\ddots&\vdots\\ a_{n1}&a_{n2}&\dots&a_{nn}}\;,$$

and $\vec v$ be the $n\times 1$ vector whose entries are all $1$:

$$\vec v=\pmatrix{1\\1\\\vdots\\1}\;.$$

The product $\vec u=A\vec v$ is an $n\times 1$ vector whose $i$-th entry is $$u_i=\sum_{j=1}^na_{ij}\cdot1=a_{i1}+a_{i2}+\ldots+a_{in}\;.$$ Since $d$ of the numbers $a_{i1},\dots,a_{in}$ are $1$ and the rest are $0$, $u_i=d$ for every $i$. Thus, $$\vec u=\pmatrix{d\\d\\\vdots\\d}=d\vec v\;.$$ That is, $A\vec v=d\vec v$, so by definition $\vec v$ is an eigenvector of $A$ for the eigenvalue $d$.

To show the other direction, you can try to reverse this argument; that works. Alternatively, you can assume that $G$ is not $d$-regular and show that $\vec v$ is not an eigenvector for an eigenvalue $d$; that also works and may be even easier.

-
Thanks to you too! – HipsterMathematician May 29 '12 at 21:01