Degree Matrices And The Graph Laplacian

From Adjacency to the Laplacian

The adjacency matrix records which pairs of vertices are joined, while a degree matrix records how many edges meet each vertex. Combining these matrices gives another encoding of the graph: the graph Laplacian. Its entries are simple to calculate, but they collect two different kinds of information in one matrix. This tutorial develops the entry patterns and computes the matrices for paths, cycles, and stars.

Throughout, graphs are finite and simple: they have no loops or multiple edges. Let \(G=(V,E)\) have vertices \(v_1,\dots,v_n\) in a specified order. Its adjacency matrix \(\mathbf A(G)=(a_{ij})\) has \(a_{ij}=1\) if \(v_i\) and \(v_j\) are adjacent, and \(a_{ij}=0\) otherwise. In particular, \(a_{ii}=0\). The degree \(\deg(v_i)\) is the number of vertices adjacent to \(v_i\).

Definition: The degree matrix \(\mathbf D(G)\) is the \(n\times n\) diagonal matrix whose \(i\)-th diagonal entry is \(\deg(v_i)\). The graph Laplacian is \(\mathbf L(G)=\mathbf D(G)-\mathbf A(G)\). The same vertex ordering is used for all three matrices.

The degree matrix has degree values on its diagonal and zero everywhere else. The Laplacian is obtained by subtracting the adjacency matrix entry by entry. Thus it has the degree of each vertex on the diagonal, and its off-diagonal entries record whether the corresponding vertices are adjacent. Changing the vertex ordering changes the positions of rows and columns, so an ordering must be stated when displaying a particular matrix.

The Entry Pattern

Theorem: For a finite simple graph \(G\), the Laplacian entries satisfy \(l_{ij}=\deg(v_i)\) when \(i=j\), and \(l_{ij}=-1\) when \(i\ne j\) and \(v_i v_j\in E\), and \(l_{ij}=0\) when \(i\ne j\) and \(v_i v_j\notin E\).

Proof. By definition, \(l_{ij}=d_{ij}-a_{ij}\), where \(d_{ij}\) is the \((i,j)\)-entry of \(\mathbf D(G)\). If \(i=j\), then \(d_{ii}=\deg(v_i)\) and \(a_{ii}=0\), because a simple graph has no loops. Hence \(l_{ii}=\deg(v_i)\). If \(i\ne j\) and \(v_i v_j\in E\), then \(d_{ij}=0\) because \(\mathbf D(G)\) is diagonal, while \(a_{ij}=1\); consequently \(l_{ij}=-1\). If \(i\ne j\) and \(v_i v_j\notin E\), then both entries are zero, so \(l_{ij}=0\). These cases cover all pairs of indices. \(\square\)

Because the graph is undirected, \(v_i\) is adjacent to \(v_j\) exactly when \(v_j\) is adjacent to \(v_i\). Therefore \(\mathbf A(G)\) is symmetric. The diagonal matrix \(\mathbf D(G)\) is symmetric as well, so their difference \(\mathbf L(G)\) is symmetric.

Theorem: Every row of \(\mathbf L(G)\) sums to zero. This includes graphs with isolated vertices; for the graph with no vertices, the assertion has no rows to check.

Proof. Fix a vertex \(v_i\). The sum of the entries in row \(i\) of \(\mathbf A(G)\) is \(\deg(v_i)\): each neighbor contributes one, and each non-neighbor contributes zero. The sum of row \(i\) of \(\mathbf D(G)\) is also \(\deg(v_i)\), since its only potentially nonzero entry is the diagonal entry. Subtracting the row sums gives \(\deg(v_i)-\deg(v_i)=0\), which is the row sum of row \(i\) in \(\mathbf L(G)\). If \(v_i\) is isolated, both row sums are zero by the same calculation. If \(V\) is empty, there are no row indices \(i\), so the statement is vacuously satisfied. \(\square\)

In particular, an isolated vertex contributes a zero row and a zero column to the Laplacian: its degree is zero and it is adjacent to no other vertex. A graph consisting of one isolated vertex has \(\mathbf A=\mathbf D=\mathbf L=[0]\).

Worked Matrices for Standard Graphs

Worked Example: The Path \(P_5\)

Let \(G=(V,E)\) have \(V=\{1,2,3,4,5\}\) and \(E=\{12,23,34,45\}\), so \(G=P_5\). Use vertex order \(1,2,3,4,5\). The endpoints 1 and 5 each have degree 1. Each of 2, 3, and 4 has degree 2. Thus the degree list in this order is \((1,2,2,2,1)\).

Place a 1 in the adjacency matrix at each pair of positions corresponding to an edge, and use symmetry for the reversed pair. All other entries are zero:

\mathbf A(G)= \begin{pmatrix} 0&1&0&0&0\\ 1&0&1&0&0\\ 0&1&0&1&0\\ 0&0&1&0&1\\ 0&0&0&1&0 \end{pmatrix}, \qquad \mathbf D(G)= \begin{pmatrix} 1&0&0&0&0\\ 0&2&0&0&0\\ 0&0&2&0&0\\ 0&0&0&2&0\\ 0&0&0&0&1 \end{pmatrix}.

Subtracting entry by entry gives the Laplacian. For example, its \((2,3)\)-entry is \(0-1=-1\), while its \((2,4)\)-entry is \(0-0=0\): vertices 2 and 3 are adjacent, but 2 and 4 are not.

\mathbf L(G)=\mathbf D(G)-\mathbf A(G)= \begin{pmatrix} 1&-1&0&0&0\\ -1&2&-1&0&0\\ 0&-1&2&-1&0\\ 0&0&-1&2&-1\\ 0&0&0&-1&1 \end{pmatrix}.

Check: The row sums are \(1-1=0\), \(-1+2-1=0\), \(-1+2-1=0\), \(-1+2-1=0\), and \(-1+1=0\). The diagonal entries reproduce the degree list, and the four pairs of off-diagonal \(-1\) entries correspond exactly to the four edges in \(E\).

Worked Example: The Cycle \(C_4\)

Let \(G=(V,E)\) have \(V=\{1,2,3,4\}\) and \(E=\{12,23,34,41\}\), the cycle \(C_4\). Use order \(1,2,3,4\). Each vertex has degree 2, so \(\mathbf D(G)\) has four diagonal entries equal to 2. The adjacency matrix has ones for the four listed edges, including \(41\), which gives entries in positions \((4,1)\) and \((1,4)\).

\mathbf A(G)= \begin{pmatrix} 0&1&0&1\\ 1&0&1&0\\ 0&1&0&1\\ 1&0&1&0 \end{pmatrix}, \qquad \mathbf D(G)= \begin{pmatrix} 2&0&0&0\\ 0&2&0&0\\ 0&0&2&0\\ 0&0&0&2 \end{pmatrix}.

Subtract the adjacency entries from the corresponding degree-matrix entries. The diagonal entries are \(2-0=2\); an adjacent off-diagonal pair gives \(0-1=-1\); a nonadjacent off-diagonal pair gives \(0-0=0\). Therefore

\mathbf L(G)= \begin{pmatrix} 2&-1&0&-1\\ -1&2&-1&0\\ 0&-1&2&-1\\ -1&0&-1&2 \end{pmatrix}.

Check: Each row sum is \(2-1-1=0\). There are four diagonal entries equal to 2, whose sum is \(8\); this agrees with the sum of the degrees, \(2+2+2+2=8\). The four adjacent pairs \(12,23,34,41\) each appear as a symmetric pair of \(-1\) entries, and the two nonadjacent pairs \(13,24\) appear as zeros.

Worked Example: The Star \(K_{1,4}\)

Let \(G=(V,E)\) have \(V=\{c,1,2,3,4\}\) and \(E=\{c1,c2,c3,c4\}\), so \(c\) is the center and \(1,2,3,4\) are the leaves. Use order \(c,1,2,3,4\). The center has degree 4, since it is adjacent to all four leaves. Each leaf has degree 1, since it is adjacent only to \(c\). The leaves are pairwise nonadjacent.

\mathbf A(G)= \begin{pmatrix} 0&1&1&1&1\\ 1&0&0&0&0\\ 1&0&0&0&0\\ 1&0&0&0&0\\ 1&0&0&0&0 \end{pmatrix}, \qquad \mathbf D(G)= \begin{pmatrix} 4&0&0&0&0\\ 0&1&0&0&0\\ 0&0&1&0&0\\ 0&0&0&1&0\\ 0&0&0&0&1 \end{pmatrix}.

Subtracting gives a diagonal entry \(4-0=4\) for the center and \(1-0=1\) for each leaf. Each center-leaf entry is \(0-1=-1\), and each leaf-leaf off-diagonal entry is \(0-0=0\). Hence

\mathbf L(G)= \begin{pmatrix} 4&-1&-1&-1&-1\\ -1&1&0&0&0\\ -1&0&1&0&0\\ -1&0&0&1&0\\ -1&0&0&0&1 \end{pmatrix}.

Check: The center row sums to \(4-1-1-1-1=0\). Each leaf row sums to \(-1+1=0\). The diagonal entries are the degrees \(4,1,1,1,1\), and the four pairs of \(-1\) entries record precisely the four center-to-leaf edges; there are no \(-1\) entries between leaves.

General Patterns and a Common Mistake

The examples illustrate formulas that extend to paths, cycles, and stars of other sizes. For \(P_n\) with \(n\ge2\), in the natural order along the path, the first and last diagonal entries of \(\mathbf L(P_n)\) are 1, the other diagonal entries are 2, and the entries immediately above and below the diagonal are \(-1\). All other entries are zero. For \(C_n\), where \(n\ge3\), each diagonal entry is 2, and each vertex has \(-1\) entries in the two positions corresponding to its cycle neighbors; all other off-diagonal entries are zero. For \(K_{1,r}\), where \(r\ge1\), put the center first: the first diagonal entry is \(r\), the remaining diagonal entries are 1, each center-leaf entry is \(-1\), and the leaf-leaf entries are zero.

These descriptions follow directly from the degrees and edges: the diagonal entries are degrees, and an off-diagonal entry is \(-1\) precisely for an edge. The restrictions on the parameters matter. \(P_1\) is a single isolated vertex and has Laplacian \([0]\); it does not have two distinct endpoints. A cycle in a simple graph has at least three vertices. In \(K_{1,r}\), the formula assumes \(r\ge1\); if there are no leaves, the graph is a single isolated vertex.

Common mistake: putting a zero on an adjacent off-diagonal position. For the path on \(V=\{1,2,3\}\) with \(E=\{12,23\}\), the degree of vertex 2 is 2. A mistaken calculation might put \(+1\) in position \((1,2)\), or leave it zero because the degree matrix has zero there. The degree matrix does have \(D_{12}=0\), but \(A_{12}=1\), so the correct Laplacian entry is \(L_{12}=D_{12}-A_{12}=0-1=-1\). The full matrix is

\mathbf A= \begin{pmatrix}0&1&0\\1&0&1\\0&1&0\end{pmatrix}, \qquad \mathbf D= \begin{pmatrix}1&0&0\\0&2&0\\0&0&1\end{pmatrix}, \qquad \mathbf L= \begin{pmatrix}1&-1&0\\-1&2&-1\\0&-1&1\end{pmatrix}.

The row sums are \(1-1=0\), \(-1+2-1=0\), and \(-1+1=0\), confirming the corrected entries. A reliable procedure is to form \(\mathbf D\) and \(\mathbf A\) separately, then subtract them entry by entry.

The Laplacian is useful because its diagonal immediately records degrees and its off-diagonal entries immediately identify edges. It therefore preserves a compact account of both local quantities while retaining a consistent matrix structure. For any calculation, check the diagonal against the degree list, check off-diagonal entries against the edge set, and verify that every row sums to zero. These checks detect many ordering and subtraction errors.

Check Your Understanding

For each question, state a vertex ordering before displaying a matrix.

For \(V=\{1,2,3,4\}\) and \(E=\{12,23,34\}\), write \(\mathbf D\) and \(\mathbf L\).
For \(V=\{1,2,3,4,5\}\) and \(E=\{12,23,34,45,51\}\), write the degree list and describe the diagonal entries of \(\mathbf L\).
For the star with vertices \(\{c,a,b\}\) and edges \(\{ca,cb\}\), write its Laplacian with the center first.
Explain why the Laplacian entry \(l_{ij}\) is zero when \(i\ne j\) and \(v_i,v_j\) are nonadjacent.
What are \(\mathbf A\), \(\mathbf D\), and \(\mathbf L\) for a single isolated vertex? Check the row-sum property.

Degree Matrices And The Graph Laplacian

What You'll Learn