Remarks on the Brouwer Conjecture

Oliver Knill

REVIEW 1 major objections 4 minor 1 cited by

Remarks on the Brouwer Conjecture

T0 review · 1 major / 4 minor · reviewed 2026-08-05 · deepseek-v4-flash

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

Pith's one-line read Brouwer's conjecture is proved for every connected graph whose vertex count reaches four times the square of its maximum degree.

desk verdict The connected-graph threshold theorem looks right and is new, but the abstract's 'all graphs' claim is not proven, and several less central parts need cleaning. read the letter →

arxiv 2508.07550 v2 pith:RDRLHNXT submitted 2025-08-11 math.CO cs.DM

Oliver Knill This is my paper · ORCID

classification math.COcs.DM MSC 05C5015A42

keywords BrouwerconjectureKirchhoffLaplacianeigenvaluessumoflargestquiverseigenvalueinterlacingdegreeboundsspectralgraphtheory

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

The paper targets the 20-year-old Brouwer conjecture, which says that the sum $S_k$ of the $k$ largest eigenvalues of the Kirchhoff (graph Laplacian) matrix of a graph is at most the number of edges plus $k(k+1)/2$. The main result proves this bound for every connected graph with $n$ vertices and maximum degree $d_1$ once $n \ge 4d_1^2$; in other words, all bounded-degree graphs are settled once they are large enough. The proof starts from a spanning tree, where the conjecture is already known, and shows that adding edges one at a time preserves the inequality via eigenvalue interlacing and an eigenvalue-degree bound. The paper also shows that solving the conjecture for simple graphs would automatically solve it for quivers (graphs with loops and multiple edges), with the bound adjusted by a redundancy term.

What carries the argument

The proof is carried by two ingredients. First, the interlacing lemma for edge deletion: if $H = G-e$, the eigenvalues $\mu_j$ of $H$ interlace those $\lambda_j$ of $G$, so $\mu_j \ge \lambda_{j+1}$, which lets each spectral sum of the larger graph be charged against a smaller-rank spectral sum. Second, the eigenvalue-degree bound $\lambda_k \le d_k + d_{k+1}$ for every quiver, proved in the author's earlier work, gives $\lambda_1 \le 2d_1$ and fixes the $4d_1^2$ threshold where the two cases in the induction close.

What would settle it

Find a connected graph with $n \ge 4d_1^2$ whose three largest Kirchhoff eigenvalues sum to more than $m + 6$; that single case would refute the theorem, since $k=3$ is already open. More directly, any quiver with $\lambda_k > d_k + d_{k+1}$ for some $k$ would break the key inequality on which the threshold rests.

Watch

Extended reading notes

Core claim

The central result is Theorem 3: if $G$ is connected and $n \ge 4d_1^2$, then $S_k = \sum_{j=1}^k \lambda_j \le m + k(k+1)/2 = B_k$ for every $1 \le k \le n$, with $\lambda_1 \ge \cdots \ge \lambda_n$ the Kirchhoff eigenvalues. The proof fixes a spanning tree $H_0$, which satisfies BC by a known result, and adds the missing edges one at a time. Edge deletion interlaces the spectra, so the sum for the larger graph can be bounded by a one-rank-smaller sum for the smaller graph; the split $k \ge 2d_1$ and $k \le 2d_1$ then uses $\lambda_1 \le 2d_1$ to close both cases. A second theorem shows the conditional quiver extension: if BC holds for all finite simple graphs, it holds for all quivers wit

Load-bearing premise

The whole proof depends on the published inequality that the $k$-th largest Kirchhoff eigenvalue is at most the sum of the $k$-th and $(k+1)$-st largest vertex degrees; if that bound has a counterexample, the threshold $4d_1^2$ no longer forces the two-case split that closes the induction.

Editorial extensions

If this is right

Every connected graph with bounded maximum degree satisfies the Brouwer bound once its vertex count is at least $4d_1^2$; no further structural assumptions are needed.
For a fixed degree bound $d_1$, only graphs with $n < 4d_1^2$ remain open, so the conjecture is reduced to a finite check for each maximum degree.
If the Brouwer conjecture is ever proved for finite simple graphs, the same theorem gives it for all quivers, with the bound $B_k = m + r + k(k+1)/2$ for redundant edges $r$.
Raising the Brouwer threshold $s$ above its current value $2$ would prove the conjecture for every quiver with spectral radius at most $s$ (Corollary 1).
Repeated Barycentric refinement of a triangle-free graph doubles the edge count without raising the maximum degree, so sufficiently refined graphs enter the theorem's range.

Reading between the lines

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

The constant 4 is an artifact of the coarse bound $\lambda_1 \le 2d_1$; any improvement to the spectral-radius bound would lower the threshold and cover denser families under the same induction.
Because the proof needs only a spanning tree, the connectedness hypothesis may be replaceable by a spanning-forest argument; testing that would decide whether the abstract's stronger 'all graphs' statement follows from the same method.
The edge-by-edge induction is constructive: for any graph in the range it produces an explicit order in which edges can be added while preserving the bound, so a computational certificate for large bounded-degree graphs is feasible.
The snap-reduction lemma suggests a dual induction that deletes vertices instead of adding edges, which would become a proof strategy for all graphs once the spectral radius is controlled below $k$.

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

Colleague, quick take: the real content here is Theorem 3 — for connected graphs with n ≥ 4 d1^2, the Brouwer conjecture holds. The proof is short and, as far as I can check, valid: the spanning-tree edge-addition induction with interlacing, the split at k = 2d1, and the n ≤ m+1 step all work given the cited inputs (the λ_j ≤ d_j + d_{j+1} bound from the author's [19], BC for trees, and the interlacing lemma). The quiver reduction (Theorem 2) is also fine as a simple Hadamard-perturbation observation. So there is a genuine new result here for bounded-degree graphs above a size threshold.

But the abstract and bullet list overclaim: they say BC holds for all graphs with n ≥ 4 d1^2, while Theorem 3 is proved only for connected graphs, and the proof uses connectivity essentially (spanning tree and n ≤ m+1). The reduction to components does not follow from the global bound. Example: P_32 ∪ K_4 has n = 36 and d1 = 3, so n ≥ 4d1^2, but the K_4 component has 4 < 36 vertices and the paper gives no argument for it. This is a real gap in the advertised claim, even if the connected statement is true.

Other soft spots, in decreasing order. Proposition 3 is stated as a result, but the proof explicitly breaks down at the last line ("m(H) ≥ λ1(H)^2 does not hold") — it should be labelled as a conjecture or removed. The quiver-gradient definition is inconsistent for loops: 2.1 says loops count in D, 9.10 defines the gradient to have zero entries for loops, and 9.12 uses nonzero entries. The cycle example asserts 1 + 2k ≤ k(k+1)/2, which is false at k = 1. There is a literal '?' in the Berndsen citation, and Theorem 2's proof says n(n+1)/2 where it means k(k+1)/2. None of these touch the main theorem, but a referee should flag them.

The load-bearing use of the author's own [19] (λ_j ≤ d_j + d_{j+1}) is worth a careful check, especially because the paper itself reports that an earlier bound was wrong; this one looks credible but is not machine-checked.

Who it's for: spectral graph theorists working on the Brouwer conjecture. They should know about the connected threshold result, but read the theorem statement, not the abstract. I'd send it to peer review: the core theorem deserves a serious referee, and the revision list is clear.

Referee Report

1 major / 4 minor

Summary. The paper studies Brouwer's conjecture on sums of the largest k Laplacian eigenvalues. Its main theorem (Theorem 3, §5.4) states that every connected graph with n ≥ 4d1^2 satisfies S_k ≤ m + k(k+1)/2 for all k. The proof starts from a spanning tree, uses the known tree case and edge-deletion interlacing, and adds edges back one by one; the two cases k ≥ 2d1 and k ≤ 2d1 are handled via λ1 ≤ 2d1 and n ≤ m+1. The paper also proves sandwich estimates D_k ≤ S_k ≤ 2D_k, extends BC from simple graphs to quivers via rank-one perturbations, and proves a snap-reduction lemma. The abstract, however, omits connectedness and claims the result for all graphs.

Significance. If the body theorem is correct, it is a nontrivial threshold result: Brouwer's conjecture holds for all sufficiently large connected graphs of bounded maximum degree. The interlacing edge-addition scheme is clean, and the proof is self-contained apart from three published ingredients ([14], [19], and the interlacing lemma). The paper is also honest about several speculative directions and includes reproducible code. The main weakness is the gap between the connected theorem and the unqualified abstract/§1.3 claim; until that is fixed, the advertised 'all graphs' statement is unsupported.

major comments (1)

[Abstract and §1.3 vs §5.4, Theorem 3] The abstract claims that (BC) holds for all graphs with n ≥ 4d1^2, and §1.3 states the same for all quivers, with no connectedness restriction. Theorem 3 is explicitly for connected graphs, and the proof uses connectedness essentially: it takes a spanning tree, and case (ii) invokes n ≤ m+1, which need not hold for a disconnected graph. The global condition also does not imply the same condition on each component: G = P_32 ∪ K_4 has n = 36, d1 = 3, so n ≥ 36, but the K_4 component has n_C = 4 < 36 = 4 d1(K_4)^2. Thus the theorem cannot be applied componentwise, and no other disconnected-case argument is provided. The headline claim must be corrected to the connected statement or supplied with a separate proof.

minor comments (4)

[§4.2, proof of Theorem 2] In the proof of the quiver upgrade, 'Bk = m + r + n(n+1)/2' should read 'k(k+1)/2'.
[§5.5(a)] The cycle example is misprinted: 'csc(2n/π)' should likely be csc(π/(2n)), and the inequality '1+2k ≤ k(k+1)/2' is false for k = 1,2. Since the theorem already covers these graphs for n ≥ 16, the example should be rewritten.
[§6.5, Proposition 3] The proof of Proposition 3 appears incomplete. It begins 'If G is a quiver with m vertices' even though m is also used for the edge count, and the snap-reduction step acknowledges that m(H) ≥ λ1(H)^2 may fail, which is precisely what the induction would need. Please replace this with the edge-adding induction used in Theorem 3, or delete the proposition.
[§5.2] Minor wording: 'the µl list is interlaced with the λl list' should be 'the µ list is interlaced with the λ list'.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the main theorem relies on independent published results, not on its own conclusion.

full rationale

The proof of Theorem 3 (Section 5.4) is a conditional derivation, not a circular one. It uses three load-bearing inputs: (i) the base case that trees satisfy the Brouwer conjecture, cited to Haemers–Mohammadian–Tayfeh-Rezaie [14]; (ii) the interlacing lemma for edge deletion, cited to Godsil–Royle [11] and also given a self-contained supersymmetry proof in Lemma 1; and (iii) the eigenvalue-degree bound λ_j ≤ d_j + d_{j+1}, cited to the author's earlier paper [19]. None of these inputs assumes the target statement. In particular, the bound from [19] is an independent theorem about Kirchhoff Laplacians of quivers, proved separately and not derived from the Brouwer conjecture; its use to conclude λ_1 ≤ 2d_1 and to split the induction at k = 2d_1 is a legitimate application of an external result. There is no fitted parameter, no quantity is defined in terms of the conclusion, and no uniqueness argument is imported solely from the author's own prior work. The discrepancy between the abstract's 'all graphs' phrasing and Theorem 3's connectedness hypothesis is a correctness/scope issue about the proof's applicability, not a circularity. Accordingly, the circularity score is 0.

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

Free parameters: none. The condition n >= 4 d_1^2 is a hypothesis, not a fitted constant, and no data are fitted anywhere; the experimental plots are illustrative. Axioms: the load-bearing external inputs are (i) the degree-eigenvalue bound from [19], used via lambda_1 <= 2d_1; (ii) the known result that trees satisfy BC [14], the induction base; (iii) Laplacian interlacing under edge removal [11], the engine of the induction; plus standard facts (Schur's inequality, Hadamard perturbation). Invented entities: none. 'Quiver', 'clover', 'ribbon', 'snap reduction', and 'Brouwer threshold' are definitions and framing devices without independent evidential claims.

assumptions (6)

domain assumption lambda_j <= d_j + d_{j+1} for all quivers (eigenvalue-degree bound)
Invoked at section 3.1 and used in the proof of Theorem 3 (section 5.4) via lambda_1 <= 2 d_1 to split the cases at k = 2d_1; this is a theorem from the author's prior paper [19], assumed here.
domain assumption Trees satisfy the Brouwer conjecture
Base case of the edge-restoration induction in Theorem 3 (section 5.4: 'We know (BC) holds for all trees [14]'); taken from Haemers, Mohammadian, Tayfeh-Rezaie 2010.
standard math Eigenvalues of K(G-e) interlace eigenvalues of K(G)
Lemma 1 (section 5.2), cited to Godsil-Royle Theorem 13.6.2 with a new supersymmetry proof via essential isospectrality of F^T F and FF^T plus Cauchy interlacing; this is the engine of the induction in Theorem 3.
standard math Schur's inequality D_k <= S_k for symmetric matrices
Used in Theorem 1 and Theorem 4a (sections 3.1, 9.7), relating sorted diagonal entries to sorted eigenvalues.
standard math Hadamard perturbation / Loewner monotonicity: a rank-one PSD perturbation of trace t increases partial eigenvalue sums by at most t
Appendix sections 9.14 to 9.17, used in Theorem 2 to show loop addition (trace 1) and parallel-edge addition (trace 2) preserve the inequality.
domain assumption BC holds for regular graphs
Mentioned only in the footnote (section 6.3) citing two MSc theses (Mayank [25], Berndsen [?]); used as context, not load-bearing for the main theorem.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Remarks on the Brouwer Conjecture." pith.science (2026). https://pith.science/paper/RDRLHNXT

@misc{pith2026250807550,
  author       = {Pith},
  title        = {Pith review of: Remarks on the Brouwer Conjecture},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/RDRLHNXT}},
  note         = {Machine review of arXiv:2508.07550}
}

read the original abstract

The Brouwer conjecture (BC) in spectral graph theory claims that the sum of the largest k Kirchhoff eigenvalues of a graph are bounded above by the number m of edges plus k(k+1)/2. We show that (BC) holds for all graphs with n vertices if n is larger or equal than 4 times the square of the maximal vertex degree. We also note that (BC) for graphs implies (BC) for quivers.

Figures

Figures reproduced from arXiv: 2508.07550 by the authors.

**Figure 1.** For a clover with m loops, the Brouwer is sharp λ1 = m For a ribbon, a graph n = 2 vertices and m ≥ 2 connections, the original Brouwer estimate is false because λ1 = 2m and m + 1(1 + 1)/2 = m + 1. But the modified Brouwer estimate with Bk = m + r + k(k + 1)/2 holds. 11 [PITH_FULL_IMAGE:figures/full_fig_p011_1.png] view at source ↗

**Figure 2.** A random quiver without multiple connections. It has 20 vertices, 50 edges and 30 loops. To the right, we see the eigenvalue sum list Sk = Pk j=1 λj , the upper bound using λj ≤ dj + dj−1, the lower bound both proven in [19] and the Brouwer upper bound. All except the Brouwer sequence m + k(k + 1)/2 are concave down. Dk Sk 2Dk Bk Hk [PITH_FULL_IMAGE:figures/full_fig_p013_2.png] view at source ↗

**Figure 3.** A complete graph K7 with redundancy r = 40 and m = 40+7∗6/2 = 61. Since λn = 0 for any graph without loops and for k = n − 1 we have 122 = tr(K) = Pk j=1 λj = m + k(k + 1)/2 + r = 61 + 21 + 40, the estimate is sharp here. 9.19. The Brouwer estimate is sharp also in the quiver case if we take a complete graph with multiple ribbon connections. The picture shows the case with K =          14 −1 −3 −3 −1 −3 −3 … view at source ↗

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

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

Remarks about Connection and Dirac matrices
math.CO 2026-01 conditional novelty 5.0 of 10

The eigenvalues of the connection and Dirac matrices of a finite simplicial complex are bounded above by the ordered connection and Dirac degrees, while the headline claim that the connection matrix dominates the Dira...

Reference graph

Works this paper leans on

31 extracted references · 29 canonical work pages · cited by 1 Pith paper

[19]

O. Knill. Eigenvalue bounds of the Kirchhoff Laplacian. Linear Algebra and its Applications, 701:1–21, 2024

work page 2024
[14]

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

work page 2010
[1]

Anderson and T.D

W.N. Anderson and T.D. Morley. Eigenvalues of the Laplacian of a graph. Linear and Multilinear Algebra, 18(2):141–145, 1985

work page 1985
[2]

Balakrishnan and K

R. Balakrishnan and K. Ranganathan. A textbook of Graph Theory. Springer, 2012

work page 2012
[3]

Brouwer and H.H Haemers

A.E. Brouwer and H.H Haemers. A lower bound for the Laplacian eigenvalues of a graph - proof of a conjecture by guo. Lin. Alg. Appl., 429:2131–2135, 2008

work page 2008
[4]

Brouwer and W.H

A.E. Brouwer and W.H. Haemers. Spectra of graphs. Springer, 2012

work page 2012
[5]

R.A. Brualdi. Introductory Combinatorics. Pearson Prantice Hall, forth edition, 2004

work page 2004
[6]

X. Chen. On Brouwer’s conjecture for the sum of k largest Laplacian eigenvalues of graphs. Linear algebra and its Applications, 578:402–410, 2019

work page 2019

Show all 31 references

[7]

J. N. Cooper. Constraints on Brouwers Laplacian spectrum conjecture. Linear Algebra Appl, 615, 2021

2021
[8]

Soci´ ete Math´ ematique de France, 1998

Y.Colin de Verdi` ere.Spectres de Graphes. Soci´ ete Math´ ematique de France, 1998

1998
[9]

B. Eckmann. Harmonische Funktionen und Randwertaufgaben in einem Komplex. Comment. Math. Helv., 17(1):240–255, 1944

1944
[10]

Tayfeh-Rezaie F

B. Tayfeh-Rezaie F. Ashraf, G.R. Omidi. On the sum of signless laplacian eigenvalues of a graph. Linear Algebra Appl., 438, 2013

2013
[11]

Godsil and G

C. Godsil and G. Royle. Algebraic Graph Theory. Springer Verlag, 2001

2001
[12]

Grone and R

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

1994
[13]

J-M. Guo. On the third largest Laplacian eigenvalue of a graph. Linear and Multilinear Algebra, 55:93–102, 2007

2007
[15]

T. Kato. Perturbation Theory for Linear Operators. Springer-Verlag, second edition, 1976

1976
[16]

O. Knill. The Hydrogen identity for Laplacians. https://arxiv.org/abs/1803.01464, 2018

2018 arXiv
[17]

O. Knill. The energy of a simplicial complex. Linear Algebra and its Applications, 600:96–129, 2020

2020
[18]

O. Knill. Green functions of energized complexes. https://arxiv.org/abs/2010.09152, 2020

2010 arXiv
[20]

Zhang K.Wang, Z

S. Zhang K.Wang, Z. Lin and C. Ye. Brouwer’s conjecture for the sum of the k largest Laplacian eigenvalues of some graphs. De Gruyter Open Mathematics, 22:1–9, 2024

2024
[21]

A. Lew. Partition density, star arboricity, and sums of laplacian eigenvalues of graphs, 2024. https://arxiv.org/abs/2410.04563

2024 arXiv
[22]

A. Lew. Sums of laplacian eigenvalues and sums of degrees, 2025. https://arxiv.org/abs/2508.04209

2025 arXiv
[23]

J-S Li and Y-L. Pan. A note on the second largest eigenvalue of the Laplacian matrix of a graph. Linear and Multilinear Algebra, 48, 2000

2000
[24]

Li and J

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

2022
[25]

On variants of the Grone-Merris conjecture

Mayank. On variants of the Grone-Merris conjecture. 2010. Master Thesis Eindhoven University of Tech- nology

2010
[26]

I. Rocha. Brouwer’s conjecture holds asymptotically almost surely, 2019. https://arxiv.org/abs/1906.05368

2019 arXiv
[27]

I. Rocha. Brouwer’s conjecture holds asymptotically almost surely. Linear Algebra and its Applications, 597:198–205, 2020

2020
[28]

Spielman

D.A. Spielman. Spectral and algebraic graph theory. lecture notes, 2025

2025
[29]

Torres and V

G. Torres and V. Trevisan. Brouwer’s conjecture for the cartesian product of graphs. Linear Algebra and its Applications, 685:66–76, 2024

2024
[30]

Trinajstic

N. Trinajstic. Chemical Graph Theory. Mathematical chemistry series. CRC Press, 2 edition, 1992

1992
[31]

C. Vasudev. Graph Theory with Applications. New Age International Pulishers, 2006. Department of Mathematics, Harvard University, Cambridge, MA, 02138 15

2006

Pith tools

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

[1] [19]

O. Knill. Eigenvalue bounds of the Kirchhoff Laplacian. Linear Algebra and its Applications, 701:1–21, 2024

work page 2024

[2] [14]

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

work page 2010

[3] [1]

Anderson and T.D

W.N. Anderson and T.D. Morley. Eigenvalues of the Laplacian of a graph. Linear and Multilinear Algebra, 18(2):141–145, 1985

work page 1985

[4] [2]

Balakrishnan and K

R. Balakrishnan and K. Ranganathan. A textbook of Graph Theory. Springer, 2012

work page 2012

[5] [3]

Brouwer and H.H Haemers

A.E. Brouwer and H.H Haemers. A lower bound for the Laplacian eigenvalues of a graph - proof of a conjecture by guo. Lin. Alg. Appl., 429:2131–2135, 2008

work page 2008

[6] [4]

Brouwer and W.H

A.E. Brouwer and W.H. Haemers. Spectra of graphs. Springer, 2012

work page 2012

[7] [5]

R.A. Brualdi. Introductory Combinatorics. Pearson Prantice Hall, forth edition, 2004

work page 2004

[8] [6]

X. Chen. On Brouwer’s conjecture for the sum of k largest Laplacian eigenvalues of graphs. Linear algebra and its Applications, 578:402–410, 2019

work page 2019