# Spectral graph theory and connected components of graphs

We know that multiplicity of least eigenvalue of laplacian matrix of graph gives us number of connected components in graph.What is intuition behind this theorem? How do we know that this works in reality?Is there any proof of that sort?

-
Is this true? $K_{4,1}$ and $C_4 \cup K_1$ are isospectral, but have a different number of components. See here. – draks ... Apr 5 '12 at 13:42
user997704: The multiplicity of the eigenvalue zero is the number of connected components. I think the intuition is just that it's not hard to see what the corresponding eigenvectors are! $$\phantom{ asdf}$$ @drask: They're isospectral with respect to the adjacency matrix, not the Laplacian matrix. – Cam McLeman Apr 5 '12 at 14:24
Well I know it works in reality but i'm not getting its intuition anyone can please suggest introductory book on spectral graph theory? – user997704 Apr 6 '12 at 9:44

In any case, the key step in the intuition is understanding how the Laplacian matrix acts on a graph, which is probably too long to fully develop here. Here's the basics: Suppose $G$ is a graph on $n$ vertices, which we arbitrarily label $1,2,\ldots,n$. Now imagine an arbitrary $n$-vector $w$ as being an assignment of a weight to each vertex, with $w_i$ the weight on the $i$-th vertex. This perspective makes it easy to visualize the action of the Laplacian matrix on the graph in terms of moving weights from one vertex to another. Seriously, pick a small graph $G$, a vector/weight-assignment $w$, and see if you can predict what will happen to the weights once you hit that vector with the Laplacian matrix $L$. (In short, the new weight on a vertex is the degree of the vertex minus the sum of the previous weights of all adjacent vertices).
Once you've got that down, eigenvectors become much less mysterious -- they're just weight assignments $w$ such that after you do the weight-transporting procedure described above, you get a new weight assignment $\lambda w$ in which each weight got scaled by the same factor $\lambda$. In particular, an eigenvector corresponding to the eigenvalue $\lambda=0$ is just a weight assignment such that the new weights (i.e., degree minus sum of incoming weights) is zero on each vertex.
If your graph has multiple components, here's a trivial such weight-assignment: Stick a 1 on every vertex of a given connected component, and zero everywhere else. Repeat for each of the $n$ connected components and you've got an eigenbasis for the eigenvalue zero.