{"id":"52e1df4d-4be8-408f-8558-7b79f78b9239","arxiv_id":"1908.08534","paper_version":7,"verdict":"REJECT","confidence":"HIGH","novelty_score":5.0,"correctness_risk":"high","formal_verification":"none","parameter_count":0,"one_line_summary":"A purported proof of Brouwer's conjecture fails at equation (2), where a false vertex-deletion interlacing chain invalidates the recursive argument.","lead":"This paper claims a short proof of Brouwer's conjecture, a long-open bound on sums of the largest Laplacian eigenvalues of a graph. The proof's key interlacing inequality is false, so the conjecture remains open.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Equation (2)'s Laplacian interlacing is false; deleting a vertex does not make L(G-v) a principal submatrix of L(G), so the recursive reduction to a smaller counterexample collapses.","rationale":"The paper's entire argument is a minimal-counterexample recursion. The complement relation in Theorem 2.1 appears to be a real result and is not the issue; the only mechanism for producing a smaller counterexample is the interlacing chain (2). That chain is demonstrably false for the maximum-degree vertex the proof itself selects: in K_{1,3} the center is the maximum-degree vertex and the asserted inequality fails. This is an internal soundness defect, not a disagreement with a consensus bound. The reader's weakest_assumption identifies exactly the same step, and my independent check agrees. No machine-checked proof or reproducible code is present to compensate. With only the weak interlacing from [Lot07], the Case 1 inequality acquires an extra -t term and does not imply the required lower bound, so the defect cannot be written off as a missing factor of one. Because the recursive step is unsupported, Brouwer's conjecture is not proved and the Theorem 1.1 consequence does not follow. Since the reader already reached REJECT with high confidence, my read does not change the verdict.","tokens_in":2973,"tokens_out":9604,"duration_ms":94639,"concrete_test":"Compute the ordered Laplacian spectra of G=K_{1,3} and of G-v where v is the central vertex. Since mu_1(L(G-v))=0 and mu_2(L(G))=1, the chain (2) would require 0 >= 1 and fails. Equivalently, re-derive (2) from Cauchy interlacing: L(G-v) = L(G)[V minus {v}] - diag(1_{N(v)}), so the correct bound is mu_i(G) >= mu_i(G-v) >= mu_{i+1}(G) - 1; substituting this weak bound into the Case 1 summation gives an extra -t term and does not force G-v to violate the conjecture. Recompute the Case 1 inequality with the weak interlacing to verify the loss.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Equation (2) is the engine of the proof: it is used in Case 1 to assert sum_{i=1}^t mu_i(L(G-v)) >= sum_{i=1}^t mu_{i+1}(L(G)). This interlacing chain is false. For a vertex v, L(G-v) is not the principal submatrix of L(G) obtained by deleting row and column v; deleting the incident edges lowers the diagonal entry of every neighbor of v by 1, so ordinary Cauchy interlacing does not apply. The cited reference [Lot07] supports only the weaker bound mu_i(G) >= mu_i(G-v) >= mu_{i+1}(G) - 1. The star K_{1,3}, with v the maximum-degree center, is a direct counterexample: L(G) has ordered eigenvalues (4,1,1,0) and L(G-v) is the 3 by 3 zero matrix, so the asserted inequality mu_1(G-v) >= mu_2(G) reads 0 >= 1. Consequently the inequality sum mu_i(L(G-v)) >= sum mu_{i+1}(L(G)) does not follow, and the contradiction with the verified base cases [BH11] and [May] cannot be produced. The secondary premises that a minimal counterexample is non-regular and has no isolated vertices are also asserted without proof, but the central unsupported step is (2).","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":3143,"tokens_out":6415,"duration_ms":66153,"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":[{"comment":"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.","section":"§2, Eq. (2)"},{"comment":"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.","section":"§2, Case 2"},{"comment":"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.","section":"§2, proof structure"}],"minor_comments":[{"comment":"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.","section":"§1, notation"},{"comment":"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.","section":"§2, Case 1"},{"comment":"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.","section":"§2, opening"},{"comment":"The paper says 'L(G) is nonnegative'; this should read 'positive semidefinite' for clarity.","section":"General"}],"recommendation":"reject","confidential_remarks":"The central interlacing inequality of the proof is demonstrably false, as shown by the star K_{1,3} in the report. This is not a presentation issue but a fatal error in the main argument. The secondary gaps about the descent and the treatment of isolated vertices reinforce the rejection. The manuscript cannot be repaired by a minor revision; the proof strategy itself would need to be substantially reworked."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Dear colleague,\n\nThe short answer: don't spend referee time on this. The paper claims a proof of Brouwer's conjecture via a minimal-counterexample recursion: given a violating graph, either G-v or the complement of G-v violates too, contradicting known base cases. The recursion is the genuinely new part, and the complement step (Theorem 2.1) is stated and used correctly. But the engine of the recursion, equation (2), is a misstatement of Laplacian interlacing. Deleting a vertex does not produce a principal submatrix—each neighbor of the deleted vertex loses one diagonal unit—so the strong chain μ1(G) ≥ μ1(G-v) ≥ μ2(G) ≥ ... does not hold. A star K_{1,3} kills it: with the center removed, L(G-v) is the zero matrix, and the asserted μ1(G-v) ≥ μ2(G) reads 0 ≥ 1. The weaker interlacing from [Lot07] (μ_i(G) ≥ μ_i(G-v) ≥ μ_{i+1}(G)-1) is what actually holds, and it cannot get the strict inequality needed. So Case 1's first inequality, and therefore the whole contradiction, collapses.\n\nWhat else? The paper is honest in its reliance on external base cases—no circularity, and the v2 text drops the tautological v1 abstract. There are minor unproved premises: a minimal counterexample is assumed non-regular and without isolated vertices, and the argument does not justify those reductions. But the central flaw is fatal and not a fixable gap.\n\nWho is this for? Someone cataloguing failed attacks on Brouwer's conjecture might want a note; the counterexample-shrinking idea is worth remembering, and the complement duality application is correct. But as a proof, it does not stand. I would not send it to referees—the counterexample to (2) is immediate on first reading.\n\nBest,\n[You]","headline":"The proof collapses because equation (2) misstates Laplacian interlacing under vertex deletion; the recursive idea is clever but cannot support the claim.","tokens_in":3791,"tokens_out":3005,"would_cite":false,"duration_ms":29297,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":false},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C50","15A42"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["Brouwer's conjecture","Laplacian eigenvalues","graph Laplacian","spectral interlacing","vertex deletion","complement graph","Laplacian energy","threshold graph"],"falsifier":"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.","tokens_in":2664,"feed_emoji":"📉","tokens_out":7777,"duration_ms":69302,"temperature":0.7,"pith_summary":"Brouwer's conjecture says that for every graph, the sum of the $t$ largest Laplacian eigenvalues is at most the number of edges plus $\\binom{t+1}{2}$. This paper tries to prove the conjecture by contradiction: assuming a smallest counterexample exists, it chooses a vertex of maximum degree and argues that either deleting that vertex or deleting a suitably chosen vertex in the complement produces a counterexample on fewer vertices. Because the conjecture is known for regular graphs and for graphs on at most ten vertices, such a descent would rule out counterexamples altogether. The whole mechanism leans on an interlacing relation between the Laplacian spectra of $G$ and $G-v$.","feed_headline":"New proof shrinks any Brouwer counterexample","feed_subtitle":"If sound, the top t Laplacian eigenvalues stay under the edge count plus (t+1 choose 2).","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the interlacing chain (2), the inequality that moves the violation from G to G-v.","marker":"[Lot07]"},{"why":"States Brouwer's conjecture and records the computer check for n≤10 that serves as base case.","marker":"[BH11]"},{"why":"Proves the conjecture for regular graphs, the second terminal case in the recursive descent.","marker":"[May]"},{"why":"Provides the complement equivalence (Theorem 2.1) used in Case 2 and earlier eigenvalue-sum bounds.","marker":"[HMTR10]"},{"why":"Gives the proof of the complement equivalence that the paper cites for Theorem 2.1.","marker":"[Che19]"}],"fun_headline_variants":["Brouwer conjecture: counterexamples can always shrink","Shrinking trick rules out Brouwer counterexamples","No smallest Brouwer violation under new reduction","Brouwer bound proved by infinite descent"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Brouwer conjecture: counterexamples can always shrink","Shrinking trick rules out Brouwer counterexamples","No smallest Brouwer violation under new reduction","Brouwer bound proved by infinite descent"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000386,"raw_usage":{"total_tokens":1946,"prompt_tokens":760,"completion_tokens":1186,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":376,"completion_tokens_details":{"reasoning_tokens":1127}},"tokens_in":376,"tokens_out":1186,"duration_ms":9726,"temperature":1.0,"reasoning_tokens":1127,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T11:39:43.481802+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[],"review_version":1}