 Graph Laplacian quadratic form

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.