Characterizing the equality case in Brouwer's inequality for Laplacian eigenvalues

Abstract

Brouwer conjectured that the sum of the $k$ largest Laplacian eigenvalues of an $n$-vertex graph is less than or equal to the number of its edges plus $\binom{k+1}{2}$ for every $k\in \{1,2,\dots,n\}$, which has been confirmed by Kothari and Tudose (2026) recently. In this note, we characterize the equality case in this inequality. Our main result is that for every $n$-vertex graph $G=(V,E)$ and for every $k\in \{1,2,\dots,n-1\}$, the equality $\sum_{i=1}^kμ_i(G)=|E(G)|+\binom{k+1}{2}$ holds if and only if $G$ is a threshold graph with clique number $k+1$, where $μ_1(G)\geq μ_2(G)\geq \cdots\geq μ_{n}(G)$ are the Laplacian eigenvalues of $G$. This, together with the confirmed Brouwer's conjecture, would yield a complete solution to the full Brouwer's conjecture posed by Li and Guo (2022). Our proof relies on the projection method of Kothari and Tudose and shows directly that the equality case can occur only for threshold graphs.

Disclosure

“e projection method of Kothari and Tudose [15]. The main difference is that we show directly that the equality case can occur only for threshold graphs by Lemma 2.3, whereas the work [4] for split graphs. Declaration of AI Use. We used GPT 5.5 Pro to simplify our proof for Lemma 2.4. References [1] H. Bai, The Grone–Merris conjecture, Trans. Amer. Math. Soc. 363 (2011), 4463–4474. [2] J. Berndsen, Three problems in algebraic combinatorics, Master’s thesis, Eindhoven Univers”

PDF page 7

Classification

Proof ideas or individual proof-step assistance

Multiplier

8

Verified

2026-08-23T18:57:48.581884Z

Structural counts