On Full Brouwer's Laplacian Conjecture

Dongxiu Cai; Jia Yang; Xiao-Dong Zhang; Zhengbo Chen

On Full Brouwer's Laplacian Conjecture

T0 review · 0 major / 4 minor · reviewed 2026-07-12 · grok-4.5

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

Pith's one-line read Equality in Brouwer's Laplacian bound holds exactly for threshold graphs of clique number k+1.

desk verdict Clean equality characterization of Brouwer after Kothari–Tudose; the projection-to-split step is the only delicate piece and it looks tight. read the letter →

arxiv 2607.03388 v1 pith:URKEARVZ submitted 2026-07-03 math.CO

Dongxiu Cai , Zhengbo Chen , Jia Yang , Xiao-Dong Zhang This is my paper · ORCID

classification math.CO MSC 05C5015A42

keywords Brouwer'sconjectureLaplacianeigenvaluessumofthresholdgraphssplitequalitycharacterizationprojectionmethod

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

Brouwer's conjecture bounds the sum of the k largest Laplacian eigenvalues of a graph by the number of edges plus a triangular number. The inequality itself was already proved; this paper settles when equality can occur. For any k between 1 and n-1, the bound is tight if and only if the graph is a threshold graph whose largest clique has size exactly k+1. The argument first forces any equality-attaining graph to be split by examining the orthogonal projection onto the top-k eigenspace, then characterises the equality case among split graphs by showing that neighbourhoods of the independent-set vertices must be nested. The result therefore supplies a complete, explicit list of the extremal graphs.

What carries the argument

The projection reduction of Kothari–Tudose: an orthogonal projection P of rank k orthogonal to the all-ones vector turns equality into sign-and-order constraints on the entries of P; those constraints force the graph to be split, after which an improved form of Bai's lemma characterises the nested-neighbourhood condition that defines threshold graphs.

What would settle it

Exhibit a non-split graph (or a split graph that is not threshold of clique number k+1) on which the sum of the k largest Laplacian eigenvalues exactly equals the number of edges plus binom(k+1,2) for some 1 ≤ k ≤ n-1.

Watch

Extended reading notes

Core claim

For every graph G on n vertices and every integer k with 1 ≤ k ≤ n-1, the sum of the k largest Laplacian eigenvalues equals e(G) + binom(k+1,2) if and only if G is a threshold graph of clique number k+1 (equivalently, G belongs to the family G_{k,r,s} for some r ≥ 1 and s ≥ 0).

Load-bearing premise

The claim that every equality-attaining pair of projection and graph must produce a split graph rests on the sign and ordering constraints extracted from the Cauchy–Schwarz and cut-sum equalities inside the projection framework.

Editorial extensions

If this is right

The only graphs that attain the Brouwer bound for a given k are completely classified: they are precisely the threshold graphs with clique number k+1.
For every split graph that is not of this form, the inequality is strict for every k.
The same characterisation recovers the already-known equality cases for trees, unicyclic graphs and other previously settled families as special cases of threshold graphs.
The complement relation for Laplacian sums immediately yields the dual characterisation for the complementary range of k.

Reading between the lines

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

The nested-neighbourhood condition that appears in the equality case is exactly the definition of a Ferrers diagram; the same combinatorial object may therefore control equality cases for related spectral majorisation inequalities.
Because the projection argument never uses more than the positive-semidefinite property and the all-ones kernel, the same technique is available for other matrix pencils whose Rayleigh quotients admit an edge-sum representation.
Once the extremal graphs are known, one can compute the precise spectral gap sk(G) - Bk(G) for every non-extremal graph by measuring how far its bipartite adjacency matrix departs from a Ferrers shape.

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

This paper finishes the equality side of Brouwer’s Laplacian conjecture: for 1 ≤ k ≤ n-1, sk(G) = e(G) + binom(k+1,2) if and only if G is a threshold graph of clique number k+1 (i.e., one of the Gk,r,s graphs). The inequality itself is already due to Kothari–Tudose; the new content is the if-and-only-if statement that Li–Guo had formulated as the “full” conjecture.

What they do well is extract equality conditions carefully from the projection reduction. They force the sign pattern on the projection matrix P, show that any equality-attaining pair (P,G) must be a split graph (via 3 imes3 principal-minor contradictions that rule out the two forbidden neighborhood configurations), then improve Bai’s lemma for split graphs so that equality forces nested neighborhoods and therefore a threshold graph of the right clique number. The Berndsen gap-function analysis and the complement relation are used cleanly. The logical chain is written out in full and can be checked line-by-line; there are no free parameters or circular definitions.

The softest step is exactly the one the reader flagged: the reduction that equality forces a split graph (Theorem 23 via Lemmas 14–22). It rests on Cauchy–Schwarz equality plus the ordered partial-sum condition forcing c = 1/n (or v = 0), which produces the rigid sign pattern for the off-diagonal entries of P. The subsequent principal-minor arguments look correct on a careful reading, and the maximality definition of r then yields the clique–independent-set partition without missing cases. The later split-graph characterization is classical and appears correctly applied. Residual risk is the usual one for a long pure-math argument—a subtle gap in a minor or homotopy step—but nothing jumps out as broken.

This is for spectral-graph-theory people who care about Laplacian partial sums and extremal characterizations. It organizes the equality cases that the literature has been circling for a decade. I would send it to referees; the result is solid enough and the write-up transparent enough to deserve a careful check rather than a desk reject. Worth citing if you work on these bounds.

Referee Report

0 major / 4 minor

Summary. The paper confirms the full Brouwer Laplacian conjecture of Li and Guo: for a graph G on n vertices and 1 ≤ k ≤ n-1, the sum of the k largest Laplacian eigenvalues satisfies sk(G) ≤ e(G) + binom(k+1,2), with equality if and only if G is a threshold graph of clique number k+1 (equivalently G ≅ Gk,r,s). The argument first extracts equality conditions from the Kothari–Tudose orthogonal-projection reduction (Lemmas 13–17), shows that any equality-attaining pair (P,G) forces G to be split (Theorem 23 via principal-minor contradictions in Lemmas 19–22), then improves Bai’s lemma for split graphs to obtain nested neighborhoods (Lemma 24) and characterises the extremal split graphs via Berndsen’s gap function (Theorems 25–27). The inequality itself is taken from Kothari–Tudose; the contribution is the equality characterisation.

Significance. Brouwer’s conjecture is a central problem in spectral graph theory; its full equality characterisation has been open since Li–Guo (2022). Completing the characterisation after the inequality was settled is a natural and valuable contribution. The paper gives a clean two-step reduction (projection equality o split o nested-neighbourhood threshold graphs) that re-uses classical tools (Bai homotopy, Berndsen gap, Grone–Merris–Bai) in a transparent way. The principal-minor arguments that force the split partition and the refined equality extraction from Bai are technically solid and of independent interest for other Laplacian-sum problems.

minor comments (4)

[Section 3.2, Lemma 15] Section 3.2, Lemma 15: the case distinction “v = 0 versus existence of r0 with vr0 > 0 ≥ vr0+1” is correct but terse; a one-sentence reminder that the non-decreasing ordering of vi together with sum vi = 0 forces the sign change (or the zero vector) would improve readability.
[Definition 2] Definition 2 / Theorem 3: the family Gk,r,s is introduced by reference to Chen–Zi; a short self-contained sentence that these are precisely the threshold graphs of clique number k+1 with nested neighbourhoods would make the paper more self-contained.
[Lemma 24] Lemma 24: the extraction of the linear-order condition from Bai’s homotopy (especially the implication aij = 0 ⇒ vji = 0 and the subsequent contradiction for incomparable neighbourhoods) is dense; a brief schematic of the sign pattern of V would help the reader follow the argument.
Throughout: a few typographical slips (e.g., “We remains to prove”, occasional missing spaces around “=”) should be cleaned in the final version.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: equality characterization derives from independent analysis of Kothari–Tudose projection equalities plus classical Bai/Berndsen lemmas, with attainment supplied by external prior theorem.

full rationale

The paper takes the already-proved inequality sk(G) ≤ Bk(G) from Kothari–Tudose (external, 2026) as given and extracts the equality case by analyzing the Cauchy–Schwarz and Lemma-11 conditions in their projection reduction (Lemmas 13–17). The resulting sign/order constraints on the entries of the rank-k projection P force (P,G) to be a “pair,” whose 3 imes3 principal minors forbid the two non-split configurations (Lemmas 19 and 21); maximality of the largest smaller endpoint then yields a clique–independent-set partition (Theorem 23). For split graphs the equality case is recovered from an improved form of Bai’s homotopy argument (linearly ordered neighbourhoods) together with Berndsen’s gap-function analysis (Lemmas 24–27), both classical and external. Attainment for the family Gk,r,s is quoted from Li–Guo (Theorem 3), an independent earlier result; the family itself is defined combinatorially, not in terms of the spectral sum being bounded. No parameter is fitted, no uniqueness theorem is imported from the present authors, and no self-citation is load-bearing. The derivation chain is therefore self-contained against external benchmarks and exhibits no circular reduction.

Assumptions & free parameters 0 free parameters · 5 assumptions · 1 invented entities

The paper is a pure existence/characterization proof in spectral graph theory. It imports standard linear-algebra and graph-theoretic facts plus three substantial external results (Kothari–Tudose projection reduction, Bai’s lemma on split graphs, Berndsen’s gap-function analysis). No numerical parameters are fitted. The only new combinatorial objects are the already-standard threshold graphs Gk,r,s, used for the equality side.

assumptions (5)

domain assumption Kothari–Tudose projection reduction of Brouwer’s inequality to a linear-algebraic statement on orthogonal projections of rank k orthogonal to the all-ones vector (their Lemmas 5.1–5.6).
Used throughout Section 3 as the starting point for equality analysis; the present paper does not re-prove the inequality itself.
domain assumption Bai’s Lemma 6 (and its homotopy/trace machinery) relating the sum of the N largest Laplacian eigenvalues of a split graph to the conjugate degree sum when λ N≥ N.
Improved in Lemma 24; the equality extraction (nested neighborhoods) depends on the sign and support properties of the matrix V produced by Bai’s argument.
domain assumption Berndsen’s analysis of the gap function ft(G)=Bt(G)-Dt(G) and the index T(G) for split graphs (Lemmas 5–7).
Used to locate possible equality indices and to rule out equality for k eq N in split graphs.
standard math Standard facts: Laplacian eigenvalues of the complete graph, Cauchy interlacing, positive-semidefiniteness of principal submatrices of orthogonal projections, Grone–Merris–Bai theorem.
Invoked repeatedly for spectral comparisons and degree-sequence relations.
domain assumption Li–Guo theorem that every Gk,r,s attains equality sk=e+binom(k+1,2).
Supplies the “if” direction of the characterization; cited as Theorem 3.

invented entities (1)

Family Gk,r,s (threshold graphs of clique number k+1 with nested neighborhoods) independent evidence
purpose: Explicit combinatorial description of the equality cases.
Already introduced by Chen–Zi and used by Li–Guo; the present paper only proves that these (and only these) graphs attain equality. No new physical or abstract entity is postulated.

how reviews work

0 comments

Cite this review

Pith. "Pith review of On Full Brouwer's Laplacian Conjecture." pith.science (2026). https://pith.science/paper/URKEARVZ

@misc{pith2026260703388,
  author       = {Pith},
  title        = {Pith review of: On Full Brouwer's Laplacian Conjecture},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/URKEARVZ}},
  note         = {Machine review of arXiv:2607.03388}
}

abstract

Brouwer's Laplacian conjecture asserts that for any graph $G$ with $n$ vertices and $m$ edges, the sum of the $k$ largest Laplacian eigenvalues satisfies $s_k(G) \le m + \binom{k+1}{2}$ for $k=1, \ldots, n$. The conjecture has been verified for numerous graph classes and for several values of $k$. Recently, Kothari and Tudose (2026) proved the conjecture. In this paper, we prove that equality holds for some $1\le k\le n-1$ if and only if $G$ is a threshold graph with clique number $k+1$, which confirms the full Brouwer conjecture formulated by Li and Guo (2022).

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 3 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

Characterizing the equality case in Brouwer's inequality for Laplacian eigenvalues
math.CO 2026-07 accept novelty 7.0 of 10

Equality in Brouwer's Laplacian inequality holds exactly for threshold graphs with clique number k+1.
The Equality Cases for the Grone-Merris-Bai Theorem
math.CO 2026-07 accept novelty 6.0 of 10

Equality in the Grone–Merris inequality holds exactly for two families obtained by deleting edges from the first dominating block or adding edges inside the first isolated block of a threshold graph, with explicit ran...
Proofs of two conjectures on generalizations of Brouwer's Laplacian conjecture
math.CO 2026-07 accept novelty 6.0 of 10

Using the settled Brouwer Laplacian theorem, both of Lew's conjectures bounding the sum of the k largest Laplacian eigenvalues by matching number and by vertex-cover number are proved.

Reference graph

Works this paper leans on

15 extracted references · 7 canonical work pages · cited by 3 Pith papers

[1]

Jochem Berndsen

doi: 10.1090/S0002-9947-2011-05393-6. Jochem Berndsen. Three problems in algebraic combinatorics. Master’s thesis, Eindhoven University of Technology, Eindhoven, The Netherlands,

doi:10.1090/s0002-9947-2011-05393-6 2011
[2]

Xiaodan Chen

doi: 10.1016/j.laa.2018.08.003. Xiaodan Chen. On brouwer’s conjecture for the sum of k largest laplacian eigenvalues of graphs. Linear Algebra and its Applications, 578:402–410,

doi:10.1016/j.laa.2018.08.003 2018
[3]

Xiaodan Chen and Junwei Zi

doi: 10.1016/j.laa.2019.05.029. Xiaodan Chen and Junwei Zi. On the full brouwer’s conjecture on laplacian eigenvalues.Discrete Applied Mathematics, 391:32–44,

doi:10.1016/j.laa.2019.05.029 2019
[4]

Joshua N

doi: 10.1016/j.dam.2026.04.036. Joshua N. Cooper. Constraints on brouwer’s laplacian spectrum conjecture.Linear Algebra and its Applications, 615:11–27,

work page doi:10.1016/j.dam.2026.04.036 2026
[5]

Zhibin Du and Bo Zhou

doi: 10.1016/j.laa.2020.12.028. Zhibin Du and Bo Zhou. Upper bounds for the sum of laplacian eigenvalues of graphs.Linear Algebra and its Applications, 436(9):3672–3683,

work page doi:10.1016/j.laa.2020.12.028 2020
[6]

doi: 10.1016/j.laa.2012.01.007. Hilal A. Ganie, S. Pirzada, Bilal A. Rather, and Vilmar Trevisan. Further developments on brouwer’s conjecture for the sum of laplacian eigenvalues of graphs.Linear Algebra and its Applications, 588:1–18,

doi:10.1016/j.laa.2012.01.007 2012
[7]

Robert Grone and Russell Merris

doi: 10.1016/j.laa.2019.11.020. Robert Grone and Russell Merris. The laplacian spectrum of a graph ii.SIAM Journal on Discrete Mathematics, 7(2):221–229,

doi:10.1016/j.laa.2019.11.020 2019
[8]

doi: 10.1137/S0895480191222653. W. H. Haemers, A. Mohammadian, and B. Tayfeh-Rezaie. On the sum of laplacian eigenvalues of graphs.Linear Algebra and its Applications, 432(9):2214–2221,

doi:10.1137/s0895480191222653

Show all 15 references

[9]

2009.03.038

doi: 10.1016/j.laa. 2009.03.038. Pravesh K. Kothari and Stefan Tudose. On brouwer’s laplacian conjecture.arXiv preprint,

2009 doi
[10]

An approximate version of brouwer’s laplacian conjecture.arXiv preprint, 2026a

Alan Lew. An approximate version of brouwer’s laplacian conjecture.arXiv preprint, 2026a. Alan Lew. Partition density, star arboricity, and sums of laplacian eigenvalues of graphs.Journal of Combinatorial Theory, Series B, 179:71–89, 2026b. doi: 10.1016/j.jctb.2026.02.002. Wen...

2026 doi
[11]

Zhen Lin and Ke Wang

doi: 10.1016/j.disc.2022.113078. Zhen Lin and Ke Wang. The preservation property of brouwer’s conjecture.Discrete Mathematics Letters, 15:39–45,

2022 doi
[12]

doi: 10.47443/dml.2024.164. Mayank. On variants of the grone-merris conjecture. Master’s thesis, Eindhoven University of Technology, Eindhoven, The Netherlands,

2024 doi
[13]

doi: 10.1016/j.ejc.2025.104287. K. Wang, Z. Lin, S. Zhang, and C. Ye. Brouwer’s conjecture for the sum of the k largest laplacian eigenvalues of some graphs.Open Mathematics, 22(1),

2025 doi
[14]

doi: 10.1515/math-2024-0062. K. Wang, Z. Lin, S. Zhang, and C. Ye. A proof of brouwer’s conjecture for k = 3.Linear Algebra and its Applications, 736:189–213,

2024 doi
[15]

doi: 10.1016/j.laa.2026.01.026. 18

2026 doi

Pith tools

Reviewed July 12, 2026 · model on record in the stance chip above.

[1] [1]

Jochem Berndsen

doi: 10.1090/S0002-9947-2011-05393-6. Jochem Berndsen. Three problems in algebraic combinatorics. Master’s thesis, Eindhoven University of Technology, Eindhoven, The Netherlands,

doi:10.1090/s0002-9947-2011-05393-6 2011

[2] [2]

Xiaodan Chen

doi: 10.1016/j.laa.2018.08.003. Xiaodan Chen. On brouwer’s conjecture for the sum of k largest laplacian eigenvalues of graphs. Linear Algebra and its Applications, 578:402–410,

doi:10.1016/j.laa.2018.08.003 2018

[3] [3]

Xiaodan Chen and Junwei Zi

doi: 10.1016/j.laa.2019.05.029. Xiaodan Chen and Junwei Zi. On the full brouwer’s conjecture on laplacian eigenvalues.Discrete Applied Mathematics, 391:32–44,

doi:10.1016/j.laa.2019.05.029 2019

[4] [4]

Joshua N

doi: 10.1016/j.dam.2026.04.036. Joshua N. Cooper. Constraints on brouwer’s laplacian spectrum conjecture.Linear Algebra and its Applications, 615:11–27,

work page doi:10.1016/j.dam.2026.04.036 2026

[5] [5]

Zhibin Du and Bo Zhou

doi: 10.1016/j.laa.2020.12.028. Zhibin Du and Bo Zhou. Upper bounds for the sum of laplacian eigenvalues of graphs.Linear Algebra and its Applications, 436(9):3672–3683,

work page doi:10.1016/j.laa.2020.12.028 2020

[6] [6]

doi: 10.1016/j.laa.2012.01.007. Hilal A. Ganie, S. Pirzada, Bilal A. Rather, and Vilmar Trevisan. Further developments on brouwer’s conjecture for the sum of laplacian eigenvalues of graphs.Linear Algebra and its Applications, 588:1–18,

doi:10.1016/j.laa.2012.01.007 2012

[7] [7]

Robert Grone and Russell Merris

doi: 10.1016/j.laa.2019.11.020. Robert Grone and Russell Merris. The laplacian spectrum of a graph ii.SIAM Journal on Discrete Mathematics, 7(2):221–229,

doi:10.1016/j.laa.2019.11.020 2019

[8] [8]

doi: 10.1137/S0895480191222653. W. H. Haemers, A. Mohammadian, and B. Tayfeh-Rezaie. On the sum of laplacian eigenvalues of graphs.Linear Algebra and its Applications, 432(9):2214–2221,

doi:10.1137/s0895480191222653