Graph Laplacians and connectivity

Fix a finite simple undirected graph with vertices in a chosen order. Let A be its symmetric adjacency matrix and D the diagonal matrix of vertex degrees. The combinatorial Laplacian is $L=D-A$. For a real vector x of vertex values, the coordinate $(Lx)_v$ is the sum of $x_v-x_u$ over neighbors u. Every row sum is zero, so the constant vector lies in the kernel. This sign convention makes L positive semidefinite; some physical evolution equations use its negative.

Expand the quadratic form: degree terms contribute one square for each endpoint of an edge, while the symmetric adjacency terms subtract the two cross terms. Grouping by unordered edges produces a sum of squared differences. Each term is nonnegative, proving positive semidefiniteness without computing eigenvalues. With positive edge weights, multiply each squared difference by its weight and define D using weighted degrees. Zero-weight connections do not enforce agreement and should be omitted when discussing connectivity through positive-weight edges.

If $Lx=0$, then its quadratic form is zero, forcing every edge difference to vanish. Values agree along every path, so x is constant on each connected component. Conversely, any vector constant separately on each component has zero differences at every edge and therefore lies in the kernel. The component indicator vectors are independent and span all such signals. Consequently the dimension of the kernel, equivalently the multiplicity of eigenvalue zero for this real symmetric matrix, equals the number of components.

For a graph with at least two vertices, order the eigenvalues increasingly. Connectedness is equivalent to the second eigenvalue being positive, since zero is always present and no eigenvalue is negative. On a connected graph, minimize the energy among nonzero vectors orthogonal to the constant vector and divide by squared norm: the result is the second eigenvalue. Orthogonality removes the trivial constant signal, and normalization prevents shrinking a signal toward zero merely to reduce its energy.

Continuous-time diffusion obeys $x'(t)=-Lx(t)$. An eigenvector with eigenvalue $\lambda$ evolves by the factor $e^{-\lambda t}$, while component-wise constants remain unchanged. Thus a connected graph approaches one constant level, and a disconnected graph can retain different constants in different components. The conserved quantity is the ordinary sum of vertex values for this symmetric combinatorial evolution. Rates depend on the chosen edge weights and time units, while moving vertices in a drawing does not change the fixed graph’s Laplacian spectrum.

Discrete averaging uses a different operator, such as $P=I-\alpha L$ with a step size making all entries nonnegative. Its eigenvalues are $1-\alpha\lambda$, so a mode may oscillate rather than decay monotonically. On the two-vertex one-edge graph, the symmetric two-state chain with transition probability alpha has eigenvalues one and $1-2\alpha$. At alpha equal to one it alternates forever. Connectivity guarantees a unique constant direction but does not by itself guarantee convergence of every discrete-time update rule.