Energy and independence number

Hitesh Kumar; Shivaramakrishna Pragada

Energy and independence number

T0 review · 0 major / 3 minor · reviewed 2026-08-01 · deepseek-v4-flash

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

Pith's one-line read 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.

desk verdict 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. read the letter →

arxiv 2607.19817 v1 pith:LLPHPE63 submitted 2026-07-22 math.CO

Hitesh Kumar , Shivaramakrishna Pragada This is my paper · ORCID

classification math.CO MSC 05C5015A1890C22

keywords graphenergyindependencenumbervertexcoverneighbourhooddeletioninequalitysemidefiniteprogrammingspectraltheorySchurcomplementadjacencyeigenvalues

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 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.

What carries the argument

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

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

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.

Reading between the lines

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

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.

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

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.

The 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.

There 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.

Who 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.

Recommendation: send this to a serious referee. It's a major within-field result with a proof that holds up under scrutiny.

Referee Report

0 major / 3 minor

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].

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.

minor comments (3)

[Claim 2.2] 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.
[Lemma 2.2] 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 1] 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'.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the proof is self-contained modulo an external SDP lemma and a standard induction on smaller subgraphs.

full rationale

The central derivation is not circular. Theorem 1.2 is proved by induction: the induction hypothesis is applied only to G−N[v], a strictly smaller induced subgraph, never to G itself. The key imported tool is Lemma 2.1, the SDP characterization E(G) = 2 min{tr M : M⪰0, M−A⪰0}, taken from Abiad et al. [1], which is unrelated prior work and is not a self-citation of the present authors. The subsequent claims (2.1–2.3) use only spectral decomposition, Schur complements, and the SDP lemma; they do not assume the target inequality. Claim 2.2 contains a typographical AM-GM line in the printed proof, but this is a correctness slip, not circularity, and the intended inequality follows from (2.5) by the standard substitution. No fitted parameters are renamed as predictions, no uniqueness theorem is imported from the authors' own prior work, and no known result is merely relabeled. The paper's recovery of the bound E(G) ≥ 2(n−χ_f(G)) from [1] is a corollary of the stronger Theorem 1.2, not an input. Therefore the derivation chain is independent of its conclusion and receives circularity score 0.

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

There are no free parameters or invented entities; every auxiliary matrix is constructed from the adjacency spectrum. The proof leans on one imported SDP lemma and standard matrix analysis.

assumptions (4)

domain assumption Lemma 2.1: E(G)=2 min{tr M : M ⪰ 0, M−A(G) ⪰ 0} (cited from [1])
Used to bound E(G−N[v]) in Claim 2.1. It is an imported theorem, not reproven; if it required extra hypotheses, the proof would break.
standard math Spectral decomposition A=P−Q with P,Q⪰0, PQ=0, B=P+Q, B²=A²
Sets up all of Section 2; follows from the spectral theorem for symmetric matrices.
standard math Schur complement criterion for PSD matrices (P_vv>0)
Guarantees P_v⪰0 and Q_v⪰0 in Claim 2.1.
domain assumption For any v, I independent in G−N[v] implies I∪{v} independent in G
Drives the induction step (Section 3), giving α(G−N[v])≤α(G)−1.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Energy and independence number." pith.science (2026). https://pith.science/paper/LLPHPE63

@misc{pith2026260719817,
  author       = {Pith},
  title        = {Pith review of: Energy and independence number},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/LLPHPE63}},
  note         = {Machine review of arXiv:2607.19817}
}

abstract

For a graph $G$ of order $n$, with adjacency eigenvalues $\lambda_1(G) \geq \cdots \geq \lambda_n(G)$, the \emph{energy} of $G$ is defined to be \[\mathcal{E}(G)=\sum_{i=1}^{n} |\lambda_i(G)|.\] A well-known conjecture from the 1980s by Fajtlowicz states that for any graph $G$, \[\mathcal{E}(G) \ge 2\left(n-\alpha(G)\right),\] where $\alpha(G)$ denotes the independence number. We prove this conjecture.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

15 extracted references · 1 linked inside Pith

[1]

A graph energy con- jecture through the lenses of semidefinite programming, 2025

Aida Abiad, Gabriel Coutinho, Emanuel Juliano, and Luuk Reijnders. A graph energy con- jecture through the lenses of semidefinite programming, 2025. arXiv:2509.05814. 1, 2, 3

arXiv 2025
[2]

Akbari, M

S. Akbari, M. Einollahzadeh, M. M. Karkhaneei, and M. A. Nematollahi. Proof of a conjecture on the Seidel energy of graphs.European J. Combin., 86:103078, 2020. 1

2020
[3]

Akbari, S

S. Akbari, S. K¨ u¸ c¨ uk¸ cif¸ ci, H. Saveh, and E. S ¸. Yazıcı. A lower bound for the energy of graphs in terms of the vertex cover number.Discrete Mathematics, 348(11):114582, 2025. 2

2025
[4]

Aouchiche and P

M. Aouchiche and P. Hansen. A survey of automated conjectures in spectral graph theory. Linear Algebra Appl., 432(9):2293–2322, 2010. 2, 3

2010
[5]

Some history of the development of Graffiti

Ermelinda DeLaVina. Some history of the development of Graffiti. InGraphs and discovery, volume 69 ofDIMACS Ser. Discrete Math. Theoret. Comput. Sci., pages 81–118. Amer. Math. Soc., Providence, RI, 2005. 2

2005
[6]

Einollahzadeh and M

M. Einollahzadeh and M. A. Nematollahi. A short proof of Haemers’ conjecture on the Seidel energy of graphs.Linear Algebra Appl., 695:75–78, 2024. 1

2024
[7]

On conjectures of Graffiti

Siemion Fajtlowicz. On conjectures of Graffiti. II. volume 60, pages 189–197. 1987. Eigh- teenth Southeastern International Conference on Combinatorics, Graph Theory, and Comput- ing (Boca Raton, Fla., 1987). 2

1987
[8]

The energy of a graph: old and new results

Ivan Gutman. The energy of a graph: old and new results. InAlgebraic combinatorics and applications (G¨ oßweinstein, 1999), pages 196–211. Springer, Berlin, 2001. 1

1999

Show all 15 references

[9]

Survey of graph energies.Mathematics Interdisciplinary Research, 2(2):85–129, 2017

Ivan Gutman and Boris Furtula. Survey of graph energies.Mathematics Interdisciplinary Research, 2(2):85–129, 2017. 1

2017
[10]

Horn and Charles R

Roger A. Horn and Charles R. Johnson.Matrix analysis. Cambridge University Press, Cam- bridge, second edition, 2013. 4

2013
[11]

Unsolved problems in spectral graph theory.Oper

Lele Liu and Bo Ning. Unsolved problems in spectral graph theory.Oper. Res. Trans., 27(4):33–60, 2023. 2, 3

2023
[12]

Nikiforov

V. Nikiforov. Beyond graph energy: norms of graphs and matrices.Linear Algebra Appl., 506:82–138, 2016. 1 7

2016
[13]

Improved bound of graph energy in terms of vertex cover number, 2025

Aniruddha Samanta. Improved bound of graph energy in terms of vertex cover number, 2025. 2

2025
[14]

Bounds of graph energy in terms of vertex cover number.Linear Algebra Appl., 517:207–216, 2017

Long Wang and Xiaobin Ma. Bounds of graph energy in terms of vertex cover number.Linear Algebra Appl., 517:207–216, 2017. 2

2017
[15]

Springer, New York, 2005

Fuzhen Zhang.The Schur Complement and Its Applications, volume 4 ofNumerical Methods and Algorithms. Springer, New York, 2005. 4 Hitesh Kumar, Email:hitesh.kumar.math@gmail.com,hitesh kumar@sfu.ca Department of Mathematics, Simon Fraser University, Burnaby, BC V5A1S6, Canada S...

2005

Pith tools

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

[1] [1]

A graph energy con- jecture through the lenses of semidefinite programming, 2025

Aida Abiad, Gabriel Coutinho, Emanuel Juliano, and Luuk Reijnders. A graph energy con- jecture through the lenses of semidefinite programming, 2025. arXiv:2509.05814. 1, 2, 3

arXiv 2025

[2] [2]

Akbari, M

S. Akbari, M. Einollahzadeh, M. M. Karkhaneei, and M. A. Nematollahi. Proof of a conjecture on the Seidel energy of graphs.European J. Combin., 86:103078, 2020. 1

2020

[3] [3]

Akbari, S

S. Akbari, S. K¨ u¸ c¨ uk¸ cif¸ ci, H. Saveh, and E. S ¸. Yazıcı. A lower bound for the energy of graphs in terms of the vertex cover number.Discrete Mathematics, 348(11):114582, 2025. 2

2025

[4] [4]

Aouchiche and P

M. Aouchiche and P. Hansen. A survey of automated conjectures in spectral graph theory. Linear Algebra Appl., 432(9):2293–2322, 2010. 2, 3

2010

[5] [5]

Some history of the development of Graffiti

Ermelinda DeLaVina. Some history of the development of Graffiti. InGraphs and discovery, volume 69 ofDIMACS Ser. Discrete Math. Theoret. Comput. Sci., pages 81–118. Amer. Math. Soc., Providence, RI, 2005. 2

2005

[6] [6]

Einollahzadeh and M

M. Einollahzadeh and M. A. Nematollahi. A short proof of Haemers’ conjecture on the Seidel energy of graphs.Linear Algebra Appl., 695:75–78, 2024. 1

2024

[7] [7]

On conjectures of Graffiti

Siemion Fajtlowicz. On conjectures of Graffiti. II. volume 60, pages 189–197. 1987. Eigh- teenth Southeastern International Conference on Combinatorics, Graph Theory, and Comput- ing (Boca Raton, Fla., 1987). 2

1987

[8] [8]

The energy of a graph: old and new results

Ivan Gutman. The energy of a graph: old and new results. InAlgebraic combinatorics and applications (G¨ oßweinstein, 1999), pages 196–211. Springer, Berlin, 2001. 1

1999