Un grafo regular de grado k está conectado si y solamente si el k valor propio tiene multiplicidad uno

Question

Vi esta frase en Wikipedia:

Un grafo regular de grado k está conectado si y solamente si el k valor propio tiene multiplicidad uno

No pude encontrar una prueba de esa declaración, puede alguien hablarme a una prueba?

Answer 1

Cada componente de $G$ da lugar a un vector propio de valor propio $k$.

Si $v=(v_1, \ldots,v_n)$ es un vector propio de valor propio $k$, wlog. no todos los $v_i\le 0$, vamos a $m=\max\{v_i\}$ ans $S=\{i\mid v_i=m\}$. A continuación, $Av=kv$ implica que para cada una de las $i\in S$, la entrada correspondiente en $Av$ es la suma de $k$ números de $\le m$ y es igual a $km$, de ahí que todos los sumandos son $m$, es decir, $S$ es cerrado bajo adyacencia y contiene al menos un componente conectado. Restar $m$ veces el vector que es $1$ excatly en este componente conectado (que es un vector propio de valor propio $k$), para obtener un autovector con menos de cero componentes. Repitiendo este paso, vamos a ver cómo escribir el dado por el vector propio como combinación lineal de los vectores propios provenientes de los componentes conectados de $G$.