REVIEW 3 major objections 4 minor 8 references
Proof of Brouwers Conjecture (BC) for all graphs with number of vertices n > n_0 assuming that BC holds for n< n_0 for some n_0
T0 review · 3 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash
Pith's one-line read This paper claims a short proof of Brouwer's conjecture by showing any counterexample contains a vertex whose deletion (or deletion in the complement) is again a counterexample, reducing to base cases.
desk verdict The proof collapses because equation (2) misstates Laplacian interlacing under vertex deletion; the recursive idea is clever but cannot support the claim. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The proof's engine is the eigenvalue interlacing chain (2), which compares the ordered Laplacian eigenvalues of $G$ with those of $G-v$. It asserts a strict alternating dominance: $\mu_1(L(G)) \ge \mu_1(L(G-v)) \ge \mu_2(L(G)) \ge \cdots \ge \mu_t(L(G-v)) \ge \mu_{t+1}(L(G))$. The complement symmetry in Theorem 2.1 is the second engine: it translates any violation for $G$ at level $t$ into a violation for the complement at level $n-t-2$, letting Case 2 borrow the Case-1 estimate.
What would settle it
Compute the Laplacian spectra of the star $K_{1,3}$ and of $K_{1,3}$ with its center deleted: the eigenvalues change from $(4,1,1,0)$ to $(0,0,0)$. Chain (2) then forces $0 \ge 1$, so the interlacing statement is false and the reduction to a smaller counterexample collapses. One spectrum check settles the soundness of the key step.
Extended reading notes
Core claim
The central claim is that any minimal counterexample can be shrunk. In Case 1, when the maximum degree $d_v(G)$ satisfies $d_v(G)+t+1 \ge n$, the proof uses interlacing to push a violation involving the top $t+1$ eigenvalues of $G$ down to a violation involving the top $t$ eigenvalues of $G-v$, adjusting the edge count by $-d_v(G)$. In Case 2, the complement relation of Theorem 2.1 converts a violation at level $t$ into a violation at level $t^* = n-t-2$ for the complement, and the same Case-1 estimate applies after deleting a low-degree vertex. If those estimates hold, the contradiction reaches the settled cases $n \le 10$ or regular graphs.
Load-bearing premise
The proof assumes that the strong interlacing chain (2) holds for every graph and vertex: deleting a vertex keeps the Laplacian eigenvalues in an alternating domination order. This is load-bearing; if it fails, the constructed smaller counterexample does not exist.
Editorial extensions
If this is right
- Brouwer's conjecture would hold for every simple graph, extending the known cases $t=1,2,n-1,n$, trees, unicyclic and bicyclic graphs, regular graphs, and $n \le 10$.
- Combined with the Helmberg–Trevisan result cited in the paper, it would imply that for fixed numbers of vertices and edges, maximum Laplacian energy is attained by a threshold graph.
- The recursive descent gives a finite certificate: checking graphs up to ten vertices would certify the bound for every larger graph.
- The complement relation would let future work transfer eigenvalue-sum bounds between a graph and its complement.
Reading between the lines
- Editorial inference: the interlacing chain (2) is not valid as stated, so this particular descent is not established; a corrected proof would need a replacement estimate linking sums of eigenvalues of $G-v$ to those of $G$.
- Editorial inference: the complement half of the recursion may survive a fix, since it relies only on Theorem 2.1 and degree counts once the Case-1 estimate is available.
- Editorial inference: the descent could be tested numerically on candidate families beyond $n=10$; if deleting a maximum-degree vertex never preserves a violation, the local interlacing route cannot be repaired.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper claims to prove Brouwer's conjecture on the sum of the t largest Laplacian eigenvalues of a simple graph. The proof strategy is by contradiction: assuming a non-regular graph G violates the conjecture for some t, the authors use an interlacing inequality to show that either G-v, where v is a vertex of maximum degree, or the complement of G minus a suitable vertex also violates the conjecture. Iterating this descent is supposed to contradict known results for n ≤ 10 and for regular graphs. The paper also states a corollary about maximum Laplacian energy being attained by threshold graphs.
Significance. Brouwer's conjecture is a well-known open problem, and a correct proof would be a significant contribution to spectral graph theory. The corollary connecting the conjecture to maximal Laplacian energy and threshold graphs is also an attractive consequence. I explicitly credit the authors for framing the argument in terms of a recursive descent and for attempting to leverage previously verified cases. However, because the central interlacing inequality used in the proof is false, the claimed result is unsupported and the paper does not, in its present form, constitute a proof.
major comments (3)
- [§2, Eq. (2)] The interlacing chain in Eq. (2) is false for the graph operation considered in the paper. The authors define G-v as the graph obtained by deleting all edges incident to v, leaving v as an isolated vertex, so L(G-v) is not a principal submatrix of L(G). For G=K_{1,3} with v the center, L(G) has eigenvalues (4,1,1,0) and L(G-v) is the 4x4 zero matrix, so the asserted inequality mu_1(L(G-v)) ≥ mu_2(L(G)) reads 0 ≥ 1. The correct weak interlacing from [Lot07] is mu_i(G) ≥ mu_i(G-v) ≥ mu_{i+1}(G)-1 (for vertex deletion), which does not imply the chain used in Case 1. Consequently the inequality sum_{i=1}^t mu_i(L(G-v)) ≥ sum_{i=1}^t mu_{i+1}(L(G)) does not follow, and the contradiction with [BH11] or [May] cannot be produced.
- [§2, Case 2] The proof assumes that the counterexample G is neither regular nor contains isolated vertices, but it is never established that a minimal counterexample has these properties. If a counterexample has an isolated vertex, the descent argument produces smaller graphs that also have isolated vertices, and the proof gives no way to handle such cases. This is a gap in the recursive strategy that is load-bearing for the claimed contradiction.
- [§2, proof structure] The recursive descent is not well-defined: in Case 1, G-v has the same number of vertices as G (v is isolated, not removed), so the recursion decreases the number of edges, not vertices. It is unclear how the process terminates in a graph with n ≤ 10 or a regular graph, especially because the intermediate graphs may contain isolated vertices, a situation explicitly excluded in Case 2. The paper needs to specify a measure of descent and prove that the process always reaches a base case.
minor comments (4)
- [§1, notation] The symbol used for the complement graph is not displayed correctly in the text; the definition of the complement appears as 'G = ...' without the overline used later in the proof.
- [§2, Case 1] The justification for mu_1(L(G)) ≤ n is garbled: the displayed relation mu_i(L(G)) = n - mu_{n-i+2}(L(bar G)) for i=2,...,n-1 does not directly bound mu_1. The bound is true for simple graphs, but the given derivation is not correct.
- [§2, opening] The restriction 'Following [HMTR10], we assume 2 ≤ t ≤ n - 2' should be justified explicitly, although the cases t=1,n-1,n are cited as known.
- [General] The paper says 'L(G) is nonnegative'; this should read 'positive semidefinite' for clarity.
Circularity Check
No circularity: the proof is a recursive reduction to externally verified base cases; its failure is a false interlacing lemma, not a circular derivation.
full rationale
The paper's recursive strategy is not circular. The base cases come from external sources: Brouwer's Conjecture for n ≤ 10 is cited to [BH11], and for regular graphs to [May]; neither is the present authors' work. The complement-equivalence Theorem 2.1 is also cited externally to [HMTR10] and [Che19]. The proof never assumes Brouwer's Conjecture for the very graph it is trying to establish, and the reduction to a smaller counterexample does not rename a fitted parameter or re-derive an input. The v1 abstract, which conditionally assumes the conjecture for n < n_0 to prove it for n > n_0, is tautological in isolation, but the v2 full text does not rely on that conditional form; it uses the fixed verified bounds n ≤ 10 and regular graphs. The actual defect is mathematical, not circular: equation (2) asserts the interlacing chain mu_1(L(G)) >= mu_1(L(G-v)) >= mu_2(L(G)) >= ... >= mu_t(L(G-v)) >= mu_{t+1}(L(G)) as a property from [Lot07], but deleting a vertex does not make L(G-v) a principal submatrix of L(G), since each neighbor of v loses one diagonal unit. For G = K_{1,3} with v the center, L(G) has ordered eigenvalues (4,1,1,0) while L(G-v) is the 3x3 zero matrix, so the asserted chain would force 0 >= 1. Thus the central step is a false lemma, not a self-referential reduction, and the circularity score is 0.
Assumptions & free parameters
assumptions (5)
- domain assumption Strong interlacing of Laplacian spectra under vertex deletion (equation (2)).
- domain assumption Base cases: Brouwer's conjecture holds for n <= 10 ([BH11]) and for regular graphs ([May]).
- ad hoc to paper A counterexample may be assumed non-regular and without isolated vertices.
- standard math Complement duality: D_s(G) = D_{n-s-1}(G-bar) (Theorem 2.1).
- standard math mu_1(L(G)) <= n for an n-vertex graph.
Cite this review
Pith. "Pith review of Proof of Brouwers Conjecture (BC) for all graphs with number of vertices n > n_0 assuming that BC holds for n< n_0 for some n_0." pith.science (2026). https://pith.science/paper/MWJSW32R
@misc{pith2026190808534,
author = {Pith},
title = {Pith review of: Proof of Brouwers Conjecture (BC) for all graphs with number of vertices n > n_0 assuming that BC holds for n< n_0 for some n_0},
year = {2026},
howpublished = {\url{https://pith.science/paper/MWJSW32R}},
note = {Machine review of arXiv:1908.08534}
}
read the original abstract
Assuming that Brouwers Conjecture the upper bound for the sum of t< n largest eigenvalues of Laplacian graph on n vertices true for n <n_0, we prove the Brouwers Conjecture BC for n > n_0 for some fixed n_0
Reference graph
Works this paper leans on
-
[1]
A. E. Brouwer and W. H. Haemers. Spectra of graphs . Springer Science & Business Media, 2011
work page 2011
-
[2]
X. Chen. On B rouwer's conjecture for the sum of k largest L aplacian eigenvalues of graphs. Linear Algebra and its Applications , 2019
work page 2019
- [3]
-
[4]
W. H. Haemers, A. Mohammadian, and B. Tayfeh-Rezaie. On the sum of L aplacian eigenvalues of graphs. Linear Algebra and its Applications , 432(9):2214--2221, 2010
work page 2010
-
[5]
C. Helmberg and V. Trevisan. Threshold graphs of maximal L aplacian energy. Discrete Mathematics , 338(7):1075--1084, 2015
work page 2015
-
[6]
Z. Lotker. Note on deleting a vertex and weak interlacing of the L aplacian spectrum. Electron. J. Linear Algebra , 16:68--72, 2007
work page 2007
- [7]
-
[8]
I. Rocha. B rouwer's conjecture holds asymptotically almost surely. arXiv:1906.05368 , 2019
arXiv 1906
Reviewed August 14, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.