Laplacian Spectra Of Regular Bipartite Graphs

Why Regularity and Bipartiteness Determine the Laplacian Endpoint

The Laplacian eigenvalues describe how a graph’s vertices are coupled through its edges. For a regular bipartite graph, two structural facts combine to determine the largest one exactly: regularity gives a simple relation between the Laplacian and adjacency matrices, while bipartiteness makes the adjacency spectrum symmetric about zero. The conclusion does not require the graph to be connected.

Throughout, graphs are finite and simple. We assume the graph has at least one vertex, so that its Laplacian has eigenvalues and a largest eigenvalue. A graph is d-regular if every vertex has degree \(d\). It is bipartite if its vertex set can be partitioned into two sets \(X\) and \(Y\) such that each edge has one endpoint in each set. Either part may contain isolated vertices.

The adjacency matrix \(\mathbf{A}(G)\) has entry \(1\) in position \(u,v\) when \(uv\) is an edge, and entry \(0\) otherwise. The degree matrix \(\mathbf{D}\) is diagonal, with \(\deg(v)\) in the position for vertex \(v\). The Laplacian is \(\mathbf{L}=\mathbf{D}-\mathbf{A}(G)\). We use the standard spectral theorem for real symmetric matrices: their eigenvalues are real, and they have a basis of eigenvectors.

The key task is therefore to find the least adjacency eigenvalue. Regularity bounds every adjacency eigenvalue between \(-d\) and \(d\); bipartiteness ensures that \(-d\) is actually attained.

Symmetry of the Adjacency Spectrum

Proof. Fix a bipartition \(X,Y\). Define a diagonal matrix \(\mathbf{S}\) whose diagonal entry is \(1\) for a vertex in \(X\) and \(-1\) for a vertex in \(Y\). Then \(\mathbf{S}^2=\mathbf{I}\). For adjacent vertices \(u,v\), the diagonal signs at \(u,v\) are opposite, so the \(u,v\) entry of \(\mathbf{S}\mathbf{A}(G)\mathbf{S}\) is \(-1\). For nonadjacent vertices that entry is \(0\). Hence \(\mathbf{S}\mathbf{A}(G)\mathbf{S}=-\mathbf{A}(G)\), or equivalently \(\mathbf{A}(G)\mathbf{S}=-\mathbf{S}\mathbf{A}(G)\). If \(\mathbf{A}(G)x=\theta x\), then \(\mathbf{A}(G)(\mathbf{S}x)=-\mathbf{S}\mathbf{A}(G)x=-\theta(\mathbf{S}x)\). Since \(\mathbf{S}\) is invertible, this correspondence preserves the dimension of each eigenspace. Thus the eigenvalues occur in opposite pairs with the same multiplicity. \(\square\)

This argument works component by component as well: choose the signs according to a bipartition of each component. Isolated vertices cause no difficulty. If the graph has no edges, the adjacency matrix is zero and the claimed symmetry still holds.

The Largest Laplacian Eigenvalue

Proof. First suppose \(d\ge 0\), and let \(x\) be a nonzero real vector. Since \(\mathbf{A}(G)\) is symmetric, its eigenvalues are real. Also, \[ x^{T}\mathbf{A}(G)x=2\sum_{uv\in E(G)}x_u x_v. \] For each edge, \(2|x_u x_v|\le x_u^2+x_v^2\). Summing this inequality over the edges gives \[ \left|x^{T}\mathbf{A}(G)x\right| \le \sum_{uv\in E(G)}(x_u^2+x_v^2) = d\sum_{v\in V(G)}x_v^2. \] The last equality holds because each vertex occurs in exactly \(d\) edges. If \(x\) is an eigenvector with eigenvalue \(\theta\), division by \(x^Tx>0\) gives \(|\theta|\le d\).

The all-ones vector is an adjacency eigenvector with eigenvalue \(d\), since every row of \(\mathbf{A}(G)\) has exactly \(d\) ones. By the lemma, \(-d\) is also an adjacency eigenvalue. The bound just proved shows that no adjacency eigenvalue is less than \(-d\); hence \(-d\) is the least adjacency eigenvalue. By \(\mathbf{L}=d\mathbf{I}-\mathbf{A}(G)\), every adjacency eigenvalue \(\theta\) gives the Laplacian eigenvalue \(d-\theta\). The largest of these is therefore \(d-(-d)=2d\), as claimed. This includes \(d=0\): then every vertex is isolated, both matrices are zero, and the largest Laplacian eigenvalue is \(0=2d\). \(\square\)

The theorem also describes the full pairing of the Laplacian spectrum. If \(\theta\) and \(-\theta\) are an adjacency eigenvalue pair, the corresponding Laplacian eigenvalues are \(d-\theta\) and \(d+\theta\). They sum to \(2d\). Thus the Laplacian eigenvalues are paired around \(d\), and the upper endpoint \(2d\) is attained.

There is a direct way to see why the endpoint is attained. Give vertices in \(X\) sign \(1\) and vertices in \(Y\) sign \(-1\), forming a vector \(s\). Every neighbor of a vertex \(v\) has sign \(-s_v\). Therefore \[ (\mathbf{L}s)_v=d s_v-\sum_{u:\,uv\in E(G)}s_u =d s_v- d(-s_v)=2d s_v. \] So \(s\) is a Laplacian eigenvector with eigenvalue \(2d\). This is the same extremal eigenvalue found through adjacency-spectrum symmetry.

Worked Examples

What the Hypotheses Do—and a Common Mistake

The regularity assumption is what makes \(\mathbf{L}=d\mathbf{I}-\mathbf{A}(G)\) hold with one constant \(d\). In an irregular graph, the degree matrix is not a scalar multiple of the identity, so subtracting adjacency eigenvalues from a single degree does not give the Laplacian spectrum. Bipartiteness supplies the opposite adjacency eigenvalue needed to attain the upper bound. The two hypotheses play different roles.

A common mistake is to conclude that every \(d\)-regular graph has largest Laplacian eigenvalue \(2d\). For a concrete counterexample, take the triangle with \(V(G)=\{1,2,3\}\) and \(E(G)=\{12,23,31\}\). It is \(2\)-regular, but not bipartite. Its Laplacian is

The all-ones vector has eigenvalue \(0\). Each vector whose coordinates sum to zero has eigenvalue \(3\), since the matrix is \(3\mathbf{I}-\mathbf{J}\), where \(\mathbf{J}\) is the all-ones matrix. Thus the Laplacian eigenvalues are \(0,3,3\), and the largest is \(3\), not \(2d=4\). The bipartite symmetry argument does not apply: the triangle’s adjacency eigenvalues are \(2,-1,-1\), which are not symmetric about zero.

For a regular bipartite graph, the useful chain of reasoning is therefore precise: regularity gives \(\mathbf{L}=d\mathbf{I}-\mathbf{A}(G)\); regularity also makes \(d\) an adjacency eigenvalue and bounds all adjacency eigenvalues in absolute value by \(d\); bipartiteness pairs \(d\) with \(-d\). Consequently, the largest Laplacian eigenvalue is exactly \(2d\), whether the graph is connected or disconnected.