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

Xiaodan Chen; Yuhang Cui

REVIEW 1 major objections 5 minor 28 references

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

T0 review · 1 major / 5 minor · reviewed 2026-08-01 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Equality in Brouwer's Laplacian inequality occurs if and only if the graph is a threshold graph with clique number k+1, the authors prove, settling the full conjecture.

desk verdict Clean equality-case proof that completes Brouwer's conjecture; the only real risk is an external lemma from the Kothari–Tudose preprint. read the letter →

arxiv 2607.17293 v1 pith:FBCJEU6S submitted 2026-07-19 math.CO

Yuhang Cui , Xiaodan Chen This is my paper · ORCID

classification math.CO MSC 05C5005C75

keywords Brouwer'sconjectureLaplacianeigenvaluessumoflargestequalitycasethresholdgraphscliquenumberprojectionmethodspectralgraphtheory

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper identifies exactly which graphs make Brouwer's inequality an equality. The claim is that for any graph and any k, the sum of the k largest Laplacian eigenvalues equals the number of edges plus the k+1 choose 2 term precisely when the graph is a threshold graph whose clique number is k+1. Because the inequality side has already been confirmed, this equality characterization completes the full version of Brouwer's conjecture. The proof works by projecting onto the top-k Laplacian eigenspace and showing that equality forces the edge structure to match the projection's sign pattern, which is then proved to be threshold. A sympathetic reader should care because it turns a numerical spectral bound into an exact structural classification with no exceptional graphs.

What carries the argument

The central object is the orthogonal projection P onto the top-k Laplacian eigenspace, together with the associated matrix M whose off-diagonal entries M_ij = P_ii + P_jj - 2P_ij - 1 lie in [-1,1]; the sign of M_ij records whether an edge is forced by the projection. Two lemmas about P form the load-bearing machinery: a sharpened inequality bounding the sum of the positive parts of the M_ij by k(k+1), and the consequence that its equality case forces the identity 1 - |M_ij| = |P_ii - P_jj| for all pairs. A further lemma shows this identity makes the graph Gamma(P), defined by M_ij > 0, a threshold graph — that is, a graph built by repeatedly adding either an isolated or a dominating vertex.

What would settle it

A single graph G and a single k for which S_k(G) = |E(G)| + binom(k+1,2) but G is not a threshold graph with clique number k+1 would falsify the theorem; a finite exhaustive search over all graphs on, say, n <= 7 vertices would settle the matter, since the theorem claims there are no exceptions.

Watch

Extended reading notes

Core claim

Theorem 1.3 states that a graph G satisfies S_k(G) = |E(G)| + binom(k+1,2) if and only if G is a threshold graph with clique number k+1. The paper's contribution is the necessity direction: if the equality holds, then G must be threshold. The argument restricts the Laplacian to the subspace orthogonal to the all-ones vector and lets P be the orthogonal projection onto the span of the top k eigenvectors. A matrix M is introduced with off-diagonal entries M_ij = P_ii + P_jj - 2P_ij - 1; the left side of the equality minus the number of edges equals the sum of M_ij over edges. Equality forces M_ij > 0 on every edge and M_ij < 0 on every non-edge, so G is exactly the graph Gamma(P) whose edges a

Load-bearing premise

The proof relies, without re-proving, on two lemmas from the recently confirmed proof of Brouwer's inequality — in particular the inequality that bounds the squared norm of a certain vector by a weighted sum of absolute differences — so if that lemma cannot be reproduced, the equality characterization collapses.

Editorial extensions

If this is right

If Theorem 1.3 is correct, the full Brouwer's conjecture is settled: the inequality holds for every graph, and the equality cases are precisely the threshold graphs of clique number k+1.
The equality condition depends on k only through the clique number: a graph can attain the bound for a given k only if its clique number is exactly k+1.
Equality forces the graph to be threshold, so any graph containing an induced P4, C4, or 2K2 — the minimal obstructions to being threshold — can never saturate the bound.
The proof shows the extremal graph G must coincide with the sign-pattern graph Gamma(P) of the projection, giving an eigenvalue-free structural criterion for equality.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

Editorial inference: the same projection-plus-sign-pattern argument may characterize equality in other Laplacian sum inequalities, such as the Grone–Merris–Bai majorization, where threshold graphs already appear as extremal cases; a unified proof of equality cases might be possible.
Editorial inference: because equality forces G = Gamma(P), the ordering of the diagonal entries P_ii may determine a vertex ordering that yields a linear-time algorithm for recognizing equality graphs directly from a Laplacian eigenvector basis.
Editorial inference: the result suggests that Brouwer's bound is tight only in the threshold-graph region; graphs far from being threshold should have slack bounded away from zero, which could support an approximate or stable version of the inequality.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Hi,

Quick take: this paper settles the equality case for Brouwer's Laplacian inequality, and it does it cleanly. The statement is exactly the natural one — equality iff threshold graph with clique number k+1. The sufficiency was already known from Li–Guo; the new content is necessity.

The proof is short. It uses Kothari–Tudose's projection method. The genuinely new piece is Lemma 2.4, an induction that starts from condition (6) and forces the projected graph to be threshold. I checked the algebra in Case 1 and it works, though the arXiv text has a few set-notation typos: in the last-row identity the sums should be over the non-neighbor set, not the neighbor set. The printed math is fine.

What's good: the paper is transparent about what it's using. It cites the two Kothari–Tudose lemmas explicitly, notes that Lemma 2.3 overlaps with Lemma 15 of concurrent work [4], and declares AI-assisted simplification of the Lemma 2.4 proof. That's the right way to write a follow-up note.

The soft spot is real but narrow. Lemma 2.2 (Kothari–Tudose's inequality between the norm of v and the weighted sum) is used without proof. It's the load-bearing external tool: equality in Lemma 2.3 forces equality in Lemma 2.2, which gives condition (6). If Lemma 2.2 is wrong, the necessity proof collapses. Kothari–Tudose is a recent arXiv preprint, so no independent verification yet. That's a dependency, not an internal flaw — Brouwer's inequality itself is now considered proved by that preprint, so relying on it for a follow-up is reasonable. But a referee should actually check Lemma 5.5 of [15], or at least confirm the Kothari–Tudose paper has passed scrutiny.

The result also leans on the Li–Guo sufficiency and the Chen–Zi clique-number fact. Those are published, so less concerning.

Overall it's a solid, honest note. The main theorem is new and the proof is convincing given the external lemmas. I'd send it to peer review. The referee's main job is to verify Lemma 2.2 and the equality-chain step that turns (8)–(9) into (6). If that holds up, this is ready to publish.

For a reading group, it's a good example of a clean equality-case argument. I'd cite it if I write about Laplacian sums.

Cheers.

Referee Report

1 major / 5 minor

Summary. The paper characterizes the equality case in Brouwer's inequality for Laplacian eigenvalues. The main result (Theorem 1.3) states that for every n-vertex graph G and every k=1,...,n-1, S_k(G)=m+binom(k+1,2) holds if and only if G is a threshold graph with clique number k+1. The proof uses the projection method introduced by Kothari and Tudose in their recent proof of Brouwer's conjecture. After introducing the projection P, the paper proves Lemma 2.3, a sharpened projection inequality with an explicit equality condition, and Lemma 2.4, which shows that any projection satisfying that equality condition defines a threshold graph Γ(P). Applying these to the top-k Laplacian eigenspace projection and using known sufficiency results yields the characterization.

Significance. If correct and once the cited proof of Brouwer's inequality is fully established, this settles the full Brouwer conjecture proposed by Li and Guo. The novelty lies in the equality analysis: Lemma 2.3 converts the global inequality into a rigid structural condition, and Lemma 2.4's induction is elegant and appears sound. The paper is transparent about its dependencies, including the recent proof by Kothari and Tudose and the concurrent work shared by Zhang's group. The proof is not machine-checked, but the reasoning is well-structured and the algebraic steps in Lemmas 2.3 and 2.4 are verifiable. The result is significant and likely to be influential.

major comments (1)

[Section 2, Lemmas 2.1 and 2.2 (cited from [15])] The necessity proof of Theorem 1.3 rests on Lemma 2.2 ([15, Lemma 5.5]), which is used to obtain inequality (10) and, in the equality case, condition (6). Lemma 2.4 then relies on (6) to conclude that Γ(P) is threshold. If Lemma 2.2 were false, the proof of Lemma 2.3 and hence the main theorem would collapse. Since [15] is a recent unreviewed arXiv preprint and no proof or independent verification is provided in this manuscript, this is a load-bearing external dependency. Please add a proof of Lemma 2.2 (and ideally Lemma 2.1, or at least a concise verification) in an appendix, or otherwise make the manuscript self-contained. Alternatively, explicitly state that the characterization is conditional on [15] and cite a published/refereed version if one becomes available.

minor comments (5)

[Lemma 2.4, Case 1, equations before (15) and in (15)] The displayed sums use the symbol N in all three places, but the derivation requires the sums to be over the complementary set \bar N (the non-neighbors of vertex n). As written with the authors' definition of N (the neighbors), the equalities are false. Please correct the notation.
[Section 2, proof of Theorem 1.3, Eq. (16)] The identity S_k(G)-m = ∑_{E} M_{ij} is taken from [15, Theorem 3.1] but not proved. This is a short trace computation; including a one-line derivation would make the paper more self-contained.
[Lemma 2.4, Case 2] The phrase 'by the same argument as in Case 1' should read 'by the induction hypothesis', since the isolated-vertex case is immediate once Γ(P') is known to be threshold.
[Abstract and Theorem 1.3] The abstract and Conjecture 1.1 state k=1,...,n, while Theorem 1.3 states k=1,...,n-1. Please clarify that equality for k=n is impossible or that this is the standard range for the full conjecture.
[Declaration of AI Use] The statement that GPT-5.5 Pro was used to simplify the proof of Lemma 2.4 may need to be adjusted to the journal's policy on AI assistance. Please ensure the description is sufficient and compliant.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity; the equality characterization is derived from independent projection-method lemmas.

full rationale

The paper's derivation chain does not reduce to its inputs. The necessity proof assumes only the equality S_k(G)=m+binom(k+1,2) and plugs it into the inequality chain (16), whose final inequality is Lemma 2.3, proved from Kothari–Tudose's Lemmas 2.1 and 2.2. Those lemmas are about arbitrary orthogonal projections and do not assume the threshold-graph conclusion. Lemma 2.3's equality condition (6) is derived from equality in the projection inequality plus Cauchy–Schwarz, not from the target structure. Lemma 2.4 is a self-contained induction showing that (6) forces Gamma(P) to be threshold. The clique-number part of the necessity is imported from published work [7] (and sufficiency from [20]); these are external results, not restatements of the paper's central claim. Even though [7] shares an author with the present paper, it is a peer-reviewed published result and is used for an auxiliary fact about threshold graphs, while the load-bearing structural threshold conclusion comes from the projection argument. The reliance on the unproved Lemma 2.2 of Kothari–Tudose is an external correctness dependency, not a circularity: no fitted parameter is renamed as a prediction, and no equation is defined in terms of the theorem to be proved.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The paper introduces no free parameters or new entities. It relies on two unproved lemmas from Kothari-Tudose [15] and two prior results for threshold graphs; these are explicit dependencies.

assumptions (4)

domain assumption Lemma 2.1 (Kothari-Tudose): For every orthogonal projection P of rank k with P1=0, 1/4 * sum_{i != j} [(M_ij+1)^2 - (P_ii - P_jj)^2] = k(k+1).
Stated without proof; proved in [15]. Used to derive Eq. (7) in Lemma 2.3.
domain assumption Lemma 2.2 (Kothari-Tudose): For every orthogonal projection P of rank k with P1=0, ||v||^2 <= sum_{i<j} (1-|M_ij|)|v_i - v_j|.
Stated without proof; proved in [15]. Central to Lemma 2.3's proof.
domain assumption Sufficiency: If G is a threshold graph with clique number k+1, then S_k(G) = m + binom(k+1,2).
Proven by Li-Guo [20]; cited in Remark 1.4. Needed for the 'if' direction of Theorem 1.3.
domain assumption Clique-number necessity for threshold graphs: If G is threshold and equality holds, then omega(G) = k+1.
Proven in [7]; cited in Remark 1.4. Needed to complete the 'only if' direction.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Characterizing the equality case in Brouwer's inequality for Laplacian eigenvalues." pith.science (2026). https://pith.science/paper/FBCJEU6S

@misc{pith2026260717293,
  author       = {Pith},
  title        = {Pith review of: Characterizing the equality case in Brouwer's inequality for Laplacian eigenvalues},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/FBCJEU6S}},
  note         = {Machine review of arXiv:2607.17293}
}

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\mu_i(G)=|E(G)|+\binom{k+1}{2}$ holds if and only if $G$ is a threshold graph with clique number $k+1$, where $\mu_1(G)\geq \mu_2(G)\geq \cdots\geq \mu_{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.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

28 extracted references · 3 linked inside Pith

[4]

D. Cai, Z. Chen, J. Yang, and X.-D. Zhang,On full Brouwer’s Laplacian conjecture, arXiv:2607.03388, 2026

arXiv 2026
[15]

P. K. Kothari and S. Tudose,On Brouwer’s Laplacian conjecture, arXiv:2606.12197, 2026

arXiv 2026
[1]

Bai,The Grone–Merris conjecture, Trans

H. Bai,The Grone–Merris conjecture, Trans. Amer. Math. Soc.363(2011), 4463–4474

2011
[2]

Berndsen,Three problems in algebraic combinatorics, Master’s thesis, Eindhoven University of Technology, 2012

J. Berndsen,Three problems in algebraic combinatorics, Master’s thesis, Eindhoven University of Technology, 2012

2012
[3]

A. E. Brouwer and W. H. Haemers,Spectra of Graphs, Springer, New York, 2012

2012
[5]

Chen,Improved results on Brouwer’s conjecture for sum of the Laplacian eigenvalues of a graph, Linear Algebra Appl.557(2018), 327–338

X. Chen,Improved results on Brouwer’s conjecture for sum of the Laplacian eigenvalues of a graph, Linear Algebra Appl.557(2018), 327–338

2018
[6]

Chen,On Brouwer’s conjecture for the sum of k largest Laplacian eigenvalues of graphs, Linear Algebra Appl.578(2019), 402–410

X. Chen,On Brouwer’s conjecture for the sum of k largest Laplacian eigenvalues of graphs, Linear Algebra Appl.578(2019), 402–410

2019
[7]

Chen and J

X. Chen and J. Zi,On the full Brouwer’s conjecture on Laplacian eigenvalues, Discrete Appl. Math.391(2026), 32–44

2026

Show all 28 references

[8]

J. N. Cooper,Constraints on Brouwer’s Laplacian spectrum conjecture, Linear Algebra Appl. 615(2021), 11–27

2021
[9]

Du and B

Z. Du and B. Zhou,Upper bounds for the sum of Laplacian eigenvalues of graphs, Linear Algebra Appl.436(2012), 3672–3683. 7

2012
[10]

H. A. Ganie, A. M. Alghamdi, and S. Pirzada,On the sum of the Laplacian eigenvalues of a graph and Brouwer’s conjecture, Linear Algebra Appl.501(2016), 376–389

2016
[11]

H. A. Ganie, S. Pirzada, B. A. Rather, and V. Trevisan,Further developments on Brouwer’s conjecture for the sum of Laplacian eigenvalues of graphs, Linear Algebra Appl.588(2020), 1–18

2020
[12]

Grone and R

R. Grone and R. Merris,The Laplacian spectrum of a graph II, SIAM J. Discrete Math.7 (1994), 221–229

1994
[13]

W. H. Haemers, A. Mohammadian, and B. Tayfeh-Rezaie,On the sum of Laplacian eigenvalues of graphs, Linear Algebra Appl.432(2010), 2214–2221

2010
[14]

Helmberg and V

C. Helmberg and V. Trevisan,Spectral threshold dominance, Brouwer’s conjecture and maxi- mality of Laplacian energy, Linear Algebra Appl.512(2016), 18–31

2016
[16]

Kumar, S

P. Kumar, S. Merajuddin, and S. Pirzada,Computing the sum of k largest Laplacian eigenvalues of tricyclic graphs, Discrete Math. Lett.11(2023), 14–18

2023
[17]

Lew,Partition density, star arboricity, and sums of laplacian eigenvalues of graphs, J

A. Lew,Partition density, star arboricity, and sums of laplacian eigenvalues of graphs, J. Combin. Theory, Ser. B179(2026), 71–89

2026
[18]

Lew,Sums of Laplacian eigenvalues and sums of degrees, arXiv:2508.04209, 2025

A. Lew,Sums of Laplacian eigenvalues and sums of degrees, arXiv:2508.04209, 2025

2025 arXiv
[19]

Lew,An approximate version of Brouwer’s Laplacian conjecture, arXiv:2601.17575, 2026

A. Lew,An approximate version of Brouwer’s Laplacian conjecture, arXiv:2601.17575, 2026

2026
[20]

Li and J.-M

W.-J. Li and J.-M. Guo,On the full Brouwer’s Laplacian spectrum conjecture, Discrete Math. 345(2022), 113078

2022
[21]

N. V. R. Mahadev and U. N. Peled,Threshold graphs and related topics, Ann. Discrete Math. 56(1995)

1995
[22]

Mayank,On variants of the Grone–Merris conjecture, Master’s thesis, Eindhoven University of Technology, Eindhoven, 2010

2010
[23]

Rocha and V

I. Rocha and V. Trevisan,Bounding the sum of the largest Laplacian eigenvalues of graphs, Discrete Appl. Math.170(2014), 95–103

2014
[24]

Rocha,Brouwer’s conjecture holds asymptotically almost surely, Linear Algebra Appl.597 (2020), 198–205

I. Rocha,Brouwer’s conjecture holds asymptotically almost surely, Linear Algebra Appl.597 (2020), 198–205

2020
[25]

G. S. Torres and V. Trevisan,Brouwer’s conjecture for the cartesian product of graphs, Linear Algebra Appl.685(2024), 66–76

2024
[26]

G. S. Torres and V. Trevisan,The critical index of Brouwer’s conjecture, Eur. J. Combin.132 (2026), 104287

2026
[27]

K. Wang, Z. Lin, S. Zhang, and C. Ye,A proof of Brouwer’s conjecture for k = 3, Linear Algebra Appl.736(2026), 189–213

2026
[28]

S. Wang, Y. Huang, and B. Liu,On a conjecture for the sum of Laplacian eigenvalues, Math. Comput. Model.56(2012), 60–68. 8

2012

Pith tools

Reviewed August 1, 2026 · model on record in the stance chip above.

[1] [4]

D. Cai, Z. Chen, J. Yang, and X.-D. Zhang,On full Brouwer’s Laplacian conjecture, arXiv:2607.03388, 2026

arXiv 2026

[2] [15]

P. K. Kothari and S. Tudose,On Brouwer’s Laplacian conjecture, arXiv:2606.12197, 2026

arXiv 2026

[3] [1]

Bai,The Grone–Merris conjecture, Trans

H. Bai,The Grone–Merris conjecture, Trans. Amer. Math. Soc.363(2011), 4463–4474

2011

[4] [2]

Berndsen,Three problems in algebraic combinatorics, Master’s thesis, Eindhoven University of Technology, 2012

J. Berndsen,Three problems in algebraic combinatorics, Master’s thesis, Eindhoven University of Technology, 2012

2012

[5] [3]

A. E. Brouwer and W. H. Haemers,Spectra of Graphs, Springer, New York, 2012

2012

[6] [5]

Chen,Improved results on Brouwer’s conjecture for sum of the Laplacian eigenvalues of a graph, Linear Algebra Appl.557(2018), 327–338

X. Chen,Improved results on Brouwer’s conjecture for sum of the Laplacian eigenvalues of a graph, Linear Algebra Appl.557(2018), 327–338

2018

[7] [6]

Chen,On Brouwer’s conjecture for the sum of k largest Laplacian eigenvalues of graphs, Linear Algebra Appl.578(2019), 402–410

X. Chen,On Brouwer’s conjecture for the sum of k largest Laplacian eigenvalues of graphs, Linear Algebra Appl.578(2019), 402–410

2019

[8] [7]

Chen and J

X. Chen and J. Zi,On the full Brouwer’s conjecture on Laplacian eigenvalues, Discrete Appl. Math.391(2026), 32–44

2026