{"id":"c819f55d-b137-4130-8792-fd431401da89","arxiv_id":"2607.19817","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":8.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"Every graph's energy is at least 2(n−α(G)), so Fajtlowicz's energy–independence conjecture is true.","lead":"This paper proves a 40-year-old conjecture: the energy of any graph is at least twice the size of a minimum vertex cover. The proof uses semidefinite programming and a new neighbourhood deletion inequality, and it implies several earlier partial results.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified; the proof is sound modulo a minor typographical slip in Claim 2.2.","rationale":"The reader's verdict of ACCEPT is justified. The reader flagged Lemma 2.1 as the weakest external dependency; I independently verified it with a short spectral argument, so it is not a substantive risk. I also checked the proof of Lemma 2.2 line by line. The decomposition argument for disconnected graphs and the treatment of isolated vertices is routine. The only real issue is a typographical error in the AM-GM step of Claim 2.2: as printed, the inequality has the wrong factor; however, the surrounding determinants and the final conclusion are correct once the intended denominator is inserted. This is an exposition error, not a flaw in the mathematics. Since it does not affect the validity of Theorem 1.2, no change to the ACCEPT verdict is needed.","tokens_in":4963,"tokens_out":19064,"duration_ms":179750,"concrete_test":"Verify the corrected Claim 2.2 algebra: set t=√(B_uu B_vv); the left side is ≥ (2/t)(t²+1−B_uv²)−4 = (2/t)((t−1)²−B_uv²). Condition (2.5) gives t≥1+|B_uv|, so the expression is nonnegative. Also check whether the published version has the denominator √xy; if not, request the typographical correction.","verdict_should_be":"UNCHANGED","load_bearing_attack":"I checked the central dependencies. Lemma 2.1 is correct: for M−N=A with M,N PSD, taking an eigenbasis of A gives tr M ≥ sum of positive eigenvalues = E/2, and M=P attains this. The induction and neighbourhood-deletion machinery are internally consistent. The only flaw I found is in the printed proof of Claim 2.2: the AM-GM line writes ≥2√xy(xy+1−z²)−4, which is false (e.g. x=y=4, z=0 gives 4.5 ≥ 64). The intended step is to use x+y≥2√xy in the form (x+y)/(xy) ≥ 2/√xy, yielding (2/√xy)(xy+1−z²)−4 = (2/√xy)((√xy−1)²−z²) ≥ 0 by (2.5). With that correction Claim 2.2 is valid. All other identities in Claims 2.1–2.3 and the induction check out. Hence the central claim is not endangered.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proves the long-standing Fajtlowicz conjecture that for every graph G of order n, E(G) ≥ 2(n − α(G)). The proof uses induction on the number of vertices, built on a 'neighbourhood deletion inequality' (Lemma 2.2): 4m + Σ_v E(G − N[v]) ≤ nE(G). The key ingredients are the semidefinite characterization of graph energy (Lemma 2.1, imported from Abiad et al.), a Schur-complement argument bounding the energy of G − N[v] by a trace term, and a summation identity involving the PSD matrix B = |A|. The authors also note several consequences: recovery of the semidefinite bound E ≥ 2(n − χ_f(\\bar G)), inertia-type bounds, and resolution of Conjecture 6.1 of [1].","tokens_in":5248,"tokens_out":8015,"duration_ms":70674,"significance":"Fajtlowicz's conjecture has been open since the 1980s and has attracted substantial recent attention. A correct proof is a significant result in spectral graph theory. The SDP-based argument is conceptually clean, and the neighbourhood-deletion inequality is an interesting tool in its own right. The proof is non-circular: the induction hypothesis is applied only to smaller induced subgraphs, no free parameters are introduced, and the only external input is the known SDP characterization of energy, which is cited. If the minor typographical issues are fixed, the argument is sound.","major_comments":[],"minor_comments":[{"comment":"The printed proof of Claim 2.2 contains a typographical error in the AM-GM step. The line reads '≥ 2√xy (xy + 1 − z²) − 4', followed by '= 2√xy ((√xy − 1)² − z²)'. Both are false as written. The correct chain is: (x+y)/(xy) ≥ 2/√xy, so the expression is ≥ (2/√xy)(xy + 1 − z²) − 4 = (2/√xy)((√xy − 1)² − z²) ≥ 0. With this correction the claim is valid.","section":"Claim 2.2"},{"comment":"The proof reduces to connected graphs but then states 'let G be a connected graph of order n ≥ 2'. The case of a connected component of order 1 (and hence isolated vertices in the decomposition) is trivial but should be mentioned explicitly, because the argument proving P_vv > 0 does not apply when n = 1.","section":"Lemma 2.2"},{"comment":"Minor wording/typos: 'appearanc' should be 'appearance'; the phrase 'the fractional chromatic number of the complement G of G' is confusing and should be rewritten, e.g., 'the fractional chromatic number of the complement of G'.","section":"Section 1"}],"recommendation":"minor_revision","confidential_remarks":null},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: this is a real proof of a 1980s conjecture that had resisted a general solution. The key new object is Lemma 2.2, the neighbourhood deletion inequality, which gives a clean inductive handle. The proof of that lemma uses the SDP characterization of energy from Abiad et al. and a spectral decomposition P−Q; the Schur complement argument in Claim 2.1 and the summation identity in Claim 2.3 check out. I went through the algebra, and the induction in Theorem 1.2 closes: you subtract the closed neighbourhood, the independence number drops by at least one, and the inequality survives. The paper also recovers the earlier results, including the fractional chromatic bound and the inertia-type bounds, and resolves Conjecture 6.1 from [1]. That's a solid contribution.\n\nThe only flaw I found is a typographical slip in the printed proof of Claim 2.2. The AM-GM step writes something that is false as written (the stress-test note gives a concrete counterexample). But the intended step works: use x+y ≥ 2√xy in the form (x+y)/(xy) ≥ 2/√xy, and the rest follows from the determinant inequality. So this is a typo, not a gap. The lemma is valid. I also note the proof depends on Lemma 2.1 from Abiad et al. as a black box; that's a reasonable import since it's a known characterization and easy to verify independently. The connected-component reduction at the start of Lemma 2.2 is handled correctly.\n\nThere are no fitted parameters and no circularity. The paper is purely mathematical, so the absence of code or data is irrelevant. The writing is dense but coherent.\n\nWho should read this: anyone working on graph energy, spectral graph theory, or semidefinite characterizations of graph parameters. It's an important result that deserves a careful referee. My honest take: accept after the typo in Claim 2.2 is fixed.\n\nRecommendation: send this to a serious referee. It's a major within-field result with a proof that holds up under scrutiny.","headline":"This paper settles the long-standing Fajtlowicz conjecture E(G) ≥ 2(n−α(G)) with a genuinely new neighbourhood deletion inequality; the proof is sound, with one minor typo in Claim 2.2.","tokens_in":5678,"tokens_out":2144,"would_cite":true,"duration_ms":21460,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C50","15A18","90C22"],"pacs":[],"model":"deepseek-v4-flash","headline":"For every finite simple graph, the graph energy is at least twice the size of a minimum vertex cover—the long-open independence-energy conjecture is now a theorem.","keywords":["graph energy","independence number","vertex cover number","neighbourhood deletion inequality","semidefinite programming","spectral graph theory","Schur complement","adjacency eigenvalues"],"falsifier":"Enumerate all graphs up to ten vertices and compute both $E(G) - 2(n - \\alpha(G))$ and the left- versus right-hand sides of the neighbourhood deletion inequality; any negative or reversed value would refute the claim. Alternatively, solve the semidefinite program of the key lemma numerically for random graphs and compare its optimum with the true energy.","tokens_in":4905,"feed_emoji":"⚡","tokens_out":7646,"duration_ms":77101,"temperature":0.7,"texified_at":"2026-08-05T21:35:00.776808+00:00","pith_summary":"The paper proves a conjecture from the 1980s: for every finite simple graph on $n$ vertices, the graph energy $E(G)$—the sum of the absolute values of the adjacency eigenvalues—is at least $2(n - \\alpha(G))$, where $\\alpha(G)$ is the independence number. Since $n - \\alpha(G)$ is exactly the minimum size of a vertex cover, this says every graph's energy is at least twice its vertex cover number. Prior results had only established weaker bounds in terms of fractional chromatic number or other spectral relaxations, so the exact statement had remained open for decades. The proof is a short induction on vertices whose key step is a new 'neighbourhood deletion inequality' relating the energy of a graph to the energies of the graphs obtained by deleting closed neighbourhoods.","texify_model":"deepseek-v4-flash","texify_usage":{"total_tokens":8402,"prompt_tokens":771,"completion_tokens":7631,"prompt_tokens_details":{"cached_tokens":0},"prompt_cache_hit_tokens":0,"prompt_cache_miss_tokens":771,"completion_tokens_details":{"reasoning_tokens":6884}},"feed_headline":"Every graph's energy is at least twice its vertex cover number","feed_subtitle":"A forty-year-old conjecture in spectral graph theory now has a proof, tying eigenvalue sums to independent sets.","key_machinery":"The engine is the semidefinite formulation $E(G) = 2 \\min\\{\\operatorname{tr} M : M \\succeq 0, M - A(G) \\succeq 0\\}$, taken as a lemma from the literature. For each vertex $v$, the authors form the positive spectral projection $P$ of the adjacency matrix and take its principal submatrix on $S(v) = V \\setminus N[v]$; after subtracting the rank-one term $x_v x_v^T / P_{vv}$ (the Schur complement), they obtain a PSD matrix $P_v$ with $P_v - A(G - N[v]) \\succeq 0$, hence a feasible witness for the energy of the deleted graph. Summing traces gives the neighbourhood deletion inequality. The decisive bookkeeping is a claim that expresses $2\\sum \\operatorname{tr}(P_v)$ as $nE(G)$ minus a sum over edges of nonnegative terms; each edge term is proved nonnegative using $2 \\times 2$ principal su","core_discovery":"The central theorem is unconditional: $E(G) \\geq 2(n - \\alpha(G))$ for every graph $G$. The proof imports a semidefinite characterization of energy—$E(G)$ equals twice the minimum trace of a positive-semidefinite matrix $M$ that also dominates the adjacency matrix—and then establishes the neighbourhood deletion inequality: $4m + \\sum_v E(G - N[v]) \\leq n E(G)$. Inducting on $n$, the authors sum the induction hypothesis over all vertices; together with $\\alpha(G - N[v]) \\leq \\alpha(G) - 1$, this plugging-in cancels the $4m$ term and yields $nE(G) \\geq 2n(n - \\alpha)$, which is exactly the desired bound.","pith_inferences":["The proof leaves the equality cases open; from the saturation conditions in the induction and the neighbourhood inequality, one would expect complete graphs, edgeless graphs, and balanced complete bipartite graphs to be the extremal family—this is an inference, not a claim of the paper.","The construction gives, for every graph and every vertex, an explicit PSD witness matrix of trace related to the energy of the deleted graph; a natural algorithmic direction not pursued here is to turn these witnesses into rounding procedures that construct large independent sets or small vertex covers.","Because the proof relies only on the semidefinite trace-minimization format and on Schur complements, the same mechanism might extend to other matrix parameters defined by similar convex relaxations, such as the energy of signed or weighted graphs.","The neighbourhood deletion inequality could be iterated inside the induction to produce refined additive lower bounds depending on finer independence structure, a route the authors do not explore."],"forward_implications":["Settles the decades-old conjecture for all finite simple graphs, not just special families.","Immediately gives E(G) ≥ 2 max{n+(G), n−(G)}, where n+ and n− count positive and negative adjacency eigenvalues, resolving the related inertia-type conjectures.","Recovers the previously strongest semidefinite bound E(G) ≥ 2(n − χ_f(\\bar G)), because the independence number is bounded above by the fractional chromatic number of the complement.","Establishes for every graph a clean combinatorial floor: graphs with large vertex cover number must have correspondingly large energy.","The neighbourhood deletion inequality is a new lower-bound tool that may itself be useful for further spectral extremal problems."],"fun_headline_variants":["1980s graph energy conjecture now proven","Every graph's energy ≥ twice its vertex cover","Eigenvalue sum bound: E(G) ≥ 2(n−α) for all G","Spectral graph theory conjecture settled after 40 years","New proof shows energy always ≥ 2 × vertex cover"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The proof's foundation is the imported semidefinite characterization of energy, $E(G) = 2 \\min\\{\\operatorname{tr} M : M \\succeq 0, M - A(G) \\succeq 0\\}$; if that identity were wrong for any graph, the induction would have no starting point.","fun_headline_variants_meta":{"raw":{"variants":["1980s graph energy conjecture now proven","Every graph's energy ≥ twice its vertex cover","Eigenvalue sum bound: E(G) ≥ 2(n−α) for all G","Spectral graph theory conjecture settled after 40 years","New proof shows energy always ≥ 2 × vertex cover"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000811,"raw_usage":{"total_tokens":3332,"prompt_tokens":617,"completion_tokens":2715,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":361,"completion_tokens_details":{"reasoning_tokens":2642}},"tokens_in":361,"tokens_out":2715,"duration_ms":23033,"temperature":1.0,"reasoning_tokens":2642,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-01T11:36:24.009044+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Enumerate all graphs up to ten vertices and compute both $E(G) - 2(n - \\alpha(G))$ and the left- versus right-hand sides of the neighbourhood deletion inequality; any negative or reversed value would refute the claim. Alternatively, solve the semidefinite program of the key lemma numerically for random graphs and compare its optimum with the true energy.","supporting_citations":[],"review_version":1}