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?
Spectral graph theory and connected components of graphs
5
$\begingroup$
graph-theory
spectral-graph-theory
-
1Is this true? $K_{4,1}$ and $C_4 \cup K_1$ are isospectral, but have a different number of components. See [here](http://en.wikipedia.org/wiki/Spectral_graph_theory). – 2012-04-05
-
1user997704: 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. – 2012-04-05
-
0Well I know it works in reality but i'm not getting its intuition anyone can please suggest introductory book on spectral graph theory? – 2012-04-06