# Spielman's proof of graph connectivity

I use Spielman's lectures on course Spectral Graph Theory

I have few question regarding Lecture 2. The Laplacian, especially Lemma 2.3.1 (Graph connectivity). Please, help me to make it a little bit clearer.

Lemma 2.3.1. Let $G=(V,E)$ be a graph, and let $0=\lambda_1 \leq \lambda_2 \leq \cdots\leq \lambda_n$ be the eigenvalues of its Laplacian matrix. Then, $\lambda_2 >0$ if and only if $G$ is connected.

Proof: We first show that $\lambda_{2}=0$ if $G$ is disconnected. If $G$ is disconnected, then it can be described as the union of two graphs, $G_{1}$ and $G_{2}$. After suitably re-numbering the vertices, we can write

$$L_{G}=\begin{bmatrix} L_{G_{1}} & 0\\ 0 & L_{G_{2}} \end{bmatrix}.$$

So, $L_{G}$ has at least two orthogonal eigenvectors of eigenvalue zero:

$$\begin{bmatrix} 0\\ 1 \end{bmatrix} \mbox{ and } \begin{bmatrix} 1\\ 0 \end{bmatrix}$$

where we have partitioned the vectors as we did the matrix $L_{G}$.

What does it mean "orthogonal eigenvectors of eigenvalue zero"? Are those eigenvalues really equal 0? How do we know that these eigenvalues correspond to $\lambda_{2}$? I suspect that all $\lambda$'s are ordered by multiplicity. But how can I prove that every $n$ by $n$ symmetric matrix has $n$ eigenvalues, counted with multiplicity.

On the other hand, assume that $G$ is connected and that $x$ is an eigenvector of $L_{G}$ of eigenvalue $0$. As $L_{G}x=0$, we have

$$x^{T}L_{G}x=\sum_{(u,v)\in E}^{} (x(u)-x(v))^{2} = 0.$$

Thus, for each pair of vertices $(u,v)$ connected by an edge, we have $x(u)=x(v)$.

Why actually it's true if $u$ and $v$ are connected by an edge, we have $x(u)=x(v)$, it's not obvious for me, even if $x$ is eigenvector, and what happens in the general case?

As every pair of vertices $u$ and $v$ are connected by a path, we may inductively apply this fact to show that $x(u)=x(v)$ for all vertices $u$ and $v$. Thus, $x$ must be a constant vector. We conclude that the eigenspace of eigenvalue $0$ has dimension $1$.

OK, by now we prove that $\lambda_{1}=0$, but what about $\lambda_{2}$?

-

What does it mean "orthogonal eigenvectors of eigenvalue zero"? Are those eigenvalues really equal 0?

Eigenvector for eigenvalue zero is a vector $\mathbf{a}$ such that $L\mathbf{a}=\mathbf{0}$. In this case $$\begin{bmatrix} L_{G_{1}} & 0\\ 0 & L_{G_{2}} \end{bmatrix} \begin{bmatrix} 0\\ 1 \end{bmatrix} = \begin{bmatrix} 0\\ 0 \end{bmatrix} \text{ and } \begin{bmatrix} L_{G_{1}} & 0\\ 0 & L_{G_{2}} \end{bmatrix} \begin{bmatrix} 1\\ 0 \end{bmatrix}= \begin{bmatrix} 0\\ 0 \end{bmatrix}$$ hence the vectors $\mathbf{a}_1=[1,\dots,1,0,\dots,0]^T$ and $\mathbf{a}_2=[0,\dots,0,1,\dots,1]^T$ are eigenvectors corresponding to eigenvalue 0.

They are orthogonal since $\mathbf{a}_1^T\mathbf{a}_2=0$. Since we know that these vectors are orthogonal, they must be linearly independent.

How do we know that these eigenvalues correspond to $\lambda_2$?

Since the eigenvalues are ordered increasingly and we have two linearly independent eigenvectors, i.e. at least two eigenvalues are zero, we know that $\lambda_1=\lambda_2=0$.

I suspect that all $\lambda$'s are ordered by multiplicity. But how can I prove that every n by n symmetric matrix has n eigenvalues, counted with multiplicity.

Eigenvalues are roots of characteristic polynomial, which has degree $n$. So, counting multiplicity, there is $n$ of them. Here we are speaking about algebraic multiplicity, see wikipedia.

Why actually it's true if $u$ and $v$ are connected by an edge, we have $x(u)=x(v)$, it's not obvious for me, even if $x$ is eigenvector, and what happens in the general case?

Since $\sum\limits_{(u,v)\in E}^{} (x(u)-x(v))^{2} = 0$ is a sum of non-negative real numbers, each of them must be zero. So we have $(x(u)-x(v))^{2}=0$ and, consequently, $(x(u)-x(v))=0$, for each $(u,v)\in E$.

OK, by now we prove that $\lambda_{1}=0$, but what about $\lambda_{2}$?

It was shown in the preceding part of the proof, that (if $G$ is connected) every eigenvector for zero is multiple of $[1,1,\dots,1]^T$. This shows that eigenspace corresponding to zero eigenvalue has dimension 1, i.e., the geometric multiplicity of this eigenvalue is 1.

EDIT: What I wrote here before was unnecessary complicated. Laplacian matrix is symmetric, hence it is diagonalizable. Thus algebraic and geometric multiplicity are the same.

However, we need to show that algebraic multiplicity of $\lambda_1=0$ is 1. Suppose this would be not true. It would imply that there exists a vector $\mathbf a$ such that $L \mathbf a = [1,1,\dots,1]^T$. This would imply that vector $[1,1,\dots,1]^T$ belongs to the column space of the matrix $L$. But directly from the definition of of Laplacian matrix we can see that this vector is orthogonal to each column of $L$. (At least for non-weighted graphs - I did not think about the weighted case.)

I agree with you that this last argument seems to be missing in the pdf-file you linked. (And probably different explanations are possible.)

Just a few words of explanation. (But it is better to read it with more details at wiki or in some linear algebra textbook.)

If $\mathbf{a}$ is an eigenvector of a matrix $A$, it means that $(A-\lambda I)\mathbf a=\mathbf 0$. If algebraic multiplicity (=the multiplicity of $\lambda$ as a root of characteristic polynomial) is greater than the geometric multiplicity (=dimension of the corresponding eigenspace), it implies that there is an eigenvector $\mathbf a$ and a generalized eigenvector $\mathbf b$ such that $(A-\lambda I)\mathbf b=\mathbf a$ .

This was the property which we used in the last paragraph.

Geometric multiplicity is precisely the number of Jordan blocks in the Jordan normal form.

It might be worth mentioning, that in the book Bapat: Graphs and Matrices, Universitext, Springer 2010, the Laplacian matrix is defined as follows. The author first defines the (vertex-edge) incidence matrix of G denoted by $Q(G)$, which is the $n\times m$ matrix with entries $0$ if the given vertex and edge are incident, $1$ if the edge starts in this vertex and $-1$ if it ends there. It is relatively easy to show that rank of $Q(G)$ is $n-k$, where $k$ is the number of connected components of this graph, see p.11-12 of this book.

Then the Laplacian matrix can be obtained as $L(G)=Q(G)Q(G)^T$, see p.45

Using this fact we get $\operatorname{rank}(L)=\operatorname{rank}(QQ^T)=\operatorname{rank}(Q)$, see Lemma 4.3, p.46.

The fact that matrix $Q$ and its Gram matrix $QQ^T$ have the same rank is mentioned in the same book on p.10 as an exercise:

Let $A$ be an $m\times n$ matrix. Show that $A$ and $A^TA$ have the same null space. Hence conclude that $\operatorname{rank} A = \operatorname{rank}A^TA$.

I.e., it was shown that $n-\operatorname{rank}(G)$ is the number of connected components. Since $L(G)$ is symmetric, it is diagonalizable, and thus this is the same as the number of non-zero eigenvalues.

Again, I do not know whether something similar can be done in the weighted case.

-
Thanks, great explanation. But I still cannot understand, in second part of the proof, we proved just if $G$ is connected than $\lambda_{1}=0$, but there is nothing about $\lambda_{2} \neq 0$. $\lambda_{1}=0$ doesn't conclude that $\lambda_{2} \neq 0$. –  com Dec 18 '11 at 18:27
Again - I tried to explain this above: It was shown that eigenspace corresponding to 0 consist only of constant vectors, i.e. multiples of [1,1,...,1]^T. This means this eigenspace is one-dimensional and the multiplicity of the eigenvalue $\lambda=0$ is $1$. (In this case, algebraic and geometric multiplicity is the same.) This is precisely the same thing as to say that $\lambda_2\ne0$. –  Martin Sleziak Dec 18 '11 at 18:31