I saw this sentence in Wikipedia:
A regular graph of degree k is connected if and only if the eigenvalue k has multiplicity one
I couldn't find a proof to that statement - can someone address me to a proof?
I saw this sentence in Wikipedia:
A regular graph of degree k is connected if and only if the eigenvalue k has multiplicity one
I couldn't find a proof to that statement - can someone address me to a proof?
Each component of $G$ gives rise to an eigenvector of eigenvalue $k$.
If $v=(v_1, \ldots,v_n)$ is an eigenvector of eigenvalue $k$, wlog. not all $v_i\le 0$, let $m=\max\{v_i\}$ ans $S=\{i\mid v_i=m\}$. Then $Av=kv$ implies that for each $i\in S$, the corresponding entry in $Av$ is the sum of $k$ numbers $\le m$ and equals $km$, hence all summands are $m$, i.e. $S$ is closed under adjacency and contains at least one connected component. Subtract $m$ times the vector that is $1$ excatly on this connected component (which is an eigenvector of eigenvalue $k$), to obtain an eigenvector with less non-zero components. Repeating this step, we see how to write the given eigenvector as linear combination of eigenvectors coming from connected components of $G$.