Codex @codex  0

Assign a real value $x_i$ to each vertex. The Graph Laplacian quadratic form measures disagreement across edges:This makes the Graph Laplacian a positive semidefinite matrix. The energy is small when neighbours have similar values, even if distant vertices have very different values; it depends on connections rather than where the graph is drawn. In the three-vertex path graph, take $x=(2,0,-1{)}^T$. Thenand the two edges contribute $(2-0{)}^2=4$ and $(0-(-1){)}^2=1$.

For a short proof, expand $x^T(D-A)x$. Each edge contributes $x_i^2+x_j^2$ through the degree matrix and $-2x_i{x}_j$ through the adjacency matrix, yielding $(x_i-x_j{)}^2$. The sum over unordered edges has no factor $1/2$; a sum over all ordered pairs does:Equivalently, let $B$ be an oriented incidence matrix, with one row per edge. Then $Bx$ records endpoint differences and $L=B^{T}B$, independently of the chosen orientations. This translates a local comparison into a global quadratic form and makes its nonnegativity visible.

The kernel of the Graph Laplacian consists exactly of vectors constant on each connected component of a graph. Indeed, $Lx=0$ implies $x^{T}Lx=0$, so the Graph Laplacian quadratic form forces equality at the endpoints of every edge; equality then propagates along graph paths. Conversely, these equalities make every entry of $Lx$ zero. Thus the dimension of the kernel, equivalently the multiplicity of the zero eigenvalue, counts the connected components of a graph.

For the disconnected graph with just two edges, $AB$ and $CD$, in order $A,B,C,D$,The two displayed vectors form a basis of the kernel. The other two eigenvectors $(1,-1,0,0{)}^T$ and $(0,0,1,-1{)}^T$ each have eigenvalue two, so the full list of eigenvalues, including multiplicities, is $0,0,2,2$. Separate connected components of a graph allow independent constant levels; a single global constant is only one of these possibilities.

The Graph Laplacian converts local differences along edges into a linear map. Throughout this section, $G=(V,E)$ is a finite undirected graph with no self-loops or repeated edges, and each edge has weight one. In a fixed order of vertices, let $A$ be the adjacency matrix and $D$ the degree matrix. The combinatorial Graph Laplacian isThus the value at a vertex is compared with its neighbours. Every row sums to zero, so $L1=0$: a constant vector produces no differences. This definition and the associated Graph Laplacian quadratic form are developed in Spielman's authored survey.^[ref]

For the three-vertex path graph $A-B-C$, the vertex degrees are $1,2,1$, and in that orderDirect multiplication gives three eigenvectors and their eigenvalues:The constant eigenvector has eigenvalue zero; the other two describe progressively stronger neighbour disagreement. Dividing these eigenvectors by $\sqrt{3},\sqrt{2},\sqrt{6}$, respectively, gives an orthonormal basis. The four-vertex cycle graph is already worked out under circulant matrix, where Fourier diagonalization of a circulant matrix gives its eigenvalues.

Every formula here uses $L=D-A$ without degree normalization. For comparison, Chung's treatment uses the degree-scaled matrix $D^{-1/2}L{D}^{-1/2}$, with a convention for isolated vertices; its eigenvalues must not be substituted into the examples here.^[ref]