Why does eigenvalue k of a regular graph of degree k have a multiplicity of one
By John Thompson
Motivation
There are lots of questions on here which link the "connectedness of a k regular graph and the multiplicity of its k eigenvalue", I understand their logic apart from the fact that they take for granted that the multiplicity of k for a connected graph is 1.
Question
How can I show eigenvalue k of a k regular graph has multiplicity of one, if it is connected?
Thoughts
It is clear that k is an eigenvalue of the eigenvector $\{1,1,\cdots,1\}$, it is also clear that vectors like $\{1,0,1,\cdots,1\}$ would have smaller eigenvalues. However what is not clear to me is why vectors like $\{1,0,2,1,\cdots,1\}$ couldn't in principle form an eigenvector.
$\endgroup$2 Answers
$\begingroup$Assume $(a_1, \ldots, a_n)$ is "another" eigenvector of eigenvalue $k$, i.e. the $a_i$ are not all equal and wlog. some are positive. Let $a=\max\{a_i\}$. Then by connectedness, there exists a vertex with value $a$ having a neighbour of value $b< a$ (you find such an edge by walking from an arbitrary vertex with value $a$ to a vertex with value $b\ne a$; such a walk exists by connectedness and there must be a first time that the path "leaves" $a$). Then the sum of the neighbours of this vertex is at most $(k-1)a+b<ka$.
$\endgroup$ 2 $\begingroup$$k$ is the spectral radius of the adjacency matrix, and thanks to Perron Frobenius Theorem, it is simple if the graph is connected, that is, the matrix is irriducible.
$\endgroup$ 3
