# The number of connected components of a $k$-regular graph equals the multiplicity of k

In similar vein to this question, I am trying to understand the proof of the fact that in a $k$-regular graph, the multiplicity of the eigenvalue $k$ equals the number of connected components.

The proof given in my book runs as follows: Let $v=(x_1,\cdots,x_n)^t$ be an eigenvector corresponding to the eigenvalue $k$ and without loss of generality suppose $|x_1|$ is maximal and $x_1>0$. Then $kx_1=\sum_{(1,j)\in E}x_j\le kx_1$. ($E$ is the edge set).

The next sentence is: This means there is no cancellation in the sum and all the $x_j's$ are equal to $x_1$. This sentence ends the proof.

I don't understand this last statement and I don't understand as to how the result follows from this.

Thanks

-

Let $G$ have $\ell$ components $C_1$, $\ldots\,$, $C_{\ell}$. For $i = 1$, $\ldots\,$, $\ell$, define the vector $x^{(i)}$ by $x^{(i)}_j = \chi_{v_j \in C_i}$.

Since the different $x^{(i)}$s are orthogonal, in order to show that the multiplicity of $k$ is $\ell$, it is enough to show that each $x^{(i)}$ is an eigenvector with eigenvalue $k$ and that if $x$ is an eigenvector with eigenvalue $k$ then there exist $\lambda_1$, $\ldots\,$, $\lambda_{\ell}$ (with some $\lambda_i \neq 0$) such that $x = \lambda_1 x^{(1)} + \cdots + \lambda_{\ell} x^{(\ell)}$.

The first assertion is easy to see. For the second, let $x$ be an eigenvector with eigenvalue $k$. Without loss of generality, assume that $\lvert x_1 \rvert$ is maximal, that $x_1 > 0$, and that $v_1 \in C_1$.

Because $x$ is an eigenvector with eigenvalue $k$, we have $$k x_1 = \sum_{(v_1,v_j)\in E} x_j.$$ Furthermore, by our hypotheses that $G$ is $k$-regular and that $\lvert x_1 \rvert$ is maximal, we have $$\sum_{(v_1,v_j)\in E} x_j \leq k \max_{(v_1,v_j)\in E} \lvert x_j \rvert \leq k x_1.$$ Note that because $G$ is $k$-regular, the sum on the left-hand side has exactly $k$ non-zero terms. Hence, all of them are positive and all equal $x_1$.

We can apply the same reasoning to each $x_j$ for which $(v_1,v_j)\in E$, and so on to all of the $x_i$ for which $v_i \in C_1$.

It may be that there exists some $j \in [n]$ such that $v_j \notin C_1$ but $x_j \neq 0$. However, we can apply the argument used above to show that for each $i$, if $v_j \in C_i$, then $x_j = \max_{v_j \in C_i} \lvert x_j \rvert$. Thus, we have shown that $x$ is a linear combination of the $x^{(i)}$s, as claimed.

-
What I don't understand is the sentence "Note that because $G$ is $k$-regular, the sum on the left-hand side has exactly $k$ non-zero terms. Hence, all of them are positive and all equal $x_1$." Could you please elaborate on that. –  Shahab Mar 25 '13 at 16:34
@Shahab We have $$k x_1 = \sum_{(v_1,v_j)\in E} x_j. \tag*{(1)}$$ Since $G$ is $k$-regular, the sum on the right-hand side has exactly $k$ terms. Thus, the average of the $x_j$s on the right-hand side of $(1)$ equals $x_1$. If any of the $x_j$s is strictly less than $x_1$, then there must exist some other $x_k$ that is strictly greater than $x_1$. However, by our hypothesis that $\lvert x_1 \rvert$ is maximal, each of the $x_j$s in the sum is less than or equal to $x_1$. Thus, no $x_j$ can be smaller than $x_1$, and all of the $x_j$s must equal $x_1$. –  Andrew Uzzell Apr 16 '13 at 19:00
Thanks for the explanation. –  Shahab Apr 17 '13 at 10:26