Spectral graph theory and connected components of graphs

Question

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?

Answer 1

I'm a little confused by your series of questions. If we "know" something, as in your first sentence, that by definition means we know it works "in reality," and also means we have a proof of that result.

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.