Graph Theory – A Finite Graph G is d-Regular if Its Adjacency Matrix Has Eigenvalue d

graph theorylinear algebraspectral-graph-theory

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…

Best Answer

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.

Related Question