Laplacian matrix

Summary

The Laplacian matrix of a finite graph is the degree matrix minus the adjacency matrix. It is symmetric and positive semidefinite, and its eigenvalues carry information about connectivity: the number of connected components is the multiplicity of the eigenvalue $0$. Through Kirchhoff's matrix tree theorem it counts spanning trees, and its second smallest eigenvalue controls how well the graph is connected. It is the discrete analogue of the Laplace operator of analysis.