# Proof of Algebraic connectivity

I am very curious about the proof of Algebraic connectivity

Algebraic connectivity:

The algebraic connectivity of a graph $G$ is the second-smallest eigenvalue of the Laplacian matrix of $G$. This eigenvalue is greater than $0$ if and only if $G$ is a connected graph.This is a corollary to the fact that the number of times $0$ appears as an eigenvalue in the Laplacian is the number of connected components in the graph.

For details : Algebraic connectivity on Wikipedia.

I found this claims very interesting, how exactly the second smallest eigenvalue can be the sign of connectivity of the graph.

Following fact not less interesting,

Denote eigenvalues by $\lambda_1 \leq \lambda_2 \leq \cdots \leq \lambda_n$, then $\lambda_1=0$.

So far I didn't the proof of Algebraic connectivity. If you have a link, I will appreciate publishing it.

Thanks!

-

Let $G = (V, E)$ be a finite graph and let $\Delta$ denote its Laplacian (here we take the convention that the Laplacian is positive semidefinite). For simplicity name the vertices $1, 2, ... n$. Then $\Delta$ is the matrix associated to the quadratic form $$q(x_1, ... x_n) = \sum_{(i, j) \in E} (x_i - x_j)^2$$
which one might call the Dirichlet energy. Recall that, for an appropriate change of variables, such a quadratic form can be written as $$q(z_1, ... z_n) = \sum_i \lambda_i z_i^2$$
where $\lambda_i$ are the eigenvalues of $\Delta$. Thus to determine the multiplicity of the zero eigenvalue it suffices to determine when $q$ can be zero. But from the first expression it should be clear that $q = 0$ if and only if $x_i = x_j$ whenever $(i, j) \in E$; that is, whenever $(x_1, ... x_n)$ determines a function $$x : V \to \mathbb{R}$$
which is constant on each connected component of $G$. The dimension of this space of functions is clearly the number of connected components of $G$, and the conclusion follows.
Thanks, quadratic form was easy to show that it works on edge. But substitution to $z$ I can't get. Could you please elaborate a little bit. And why eigenvalues shows up in the next formula –  com Dec 11 '11 at 20:56
@com: in vector notation, we can write the quadratic form as $\langle v, \Delta v \rangle$. By the spectral theorem, $\Delta$ has an orthonormal basis $v_1, ... v_n$ with eigenvalues $\lambda_1, ... \lambda_n$, and relative to this basis writing $v = \sum z_i v_i$ we get the desired representation. –  Qiaochu Yuan Dec 11 '11 at 21:04