Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Show that a graph $G$ finite 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...

share|cite|improve this question
up vote 3 down vote accepted

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.)

share|cite|improve this answer
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.

share|cite|improve this answer
Thanks to you too! – HipsterMathematician May 29 '12 at 21:01

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.