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...
A finite graph G is $d$-regular if, and only if, its adjacency matrix has the eigenvalue $λ = d$
2 Answers
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.)
-
0@HipsterMathematician Congratulations! – 2015-01-23
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.