MathDB

Fajtlowicz’s graph-energy conjecture

At least 38 years old · documented by

Let GG be a graph on nn vertices with independence number 4α(G)4\alpha(G). Let AA be the adjacency matrix of GG with eigenvalues λ1≥⋯≥λn\lambda_1\geq\cdots\geq\lambda_n. Fajtlowicz's graph energy conjecture.

∑λi>0λi=12E(G)≥n−α(G).\sum_{\lambda_i > 0} \lambda_i = \frac{1}{2}\mathcal{E}(G) \geq n-\alpha(G).

The conjecture was proposed by Fajtlowicz using Graffiti in the 1980s. It has been computationally verified for all graphs with up to 10 vertices and is known to hold for almost all graphs, but remains open in general; the paper develops a semidefinite-programming approach toward proving it.

Equivalent formulations 1Other wordings

Other statements of this same problem, merged from separate entries. Each is equivalent to the statement above — proving any one settles them all.

  1. Fajtlowicz’s graph-energy conjecture

    Does every graph of order nn and independence number α(G)\alpha(G) have energy at least 2(n−α(G))2(n-\alpha(G))?

References

Primary source

Aida Abiad, Gabriel Coutinho, Emanuel Juliano and Luuk Reijnders, “A graph energy conjecture through the lenses of semidefinite programming”, arXiv:2509.05814 (2025).

combinatoricsgraph-energysemidefinite-programmingspectral-graph-theory
Posted

Progress summary

Refreshed
Claimed solved

A 2026 arXiv paper proves the conjecture for every graph, ending the longstanding open problem.

Fajtlowicz proposed in the 1980s, using Graffiti, that every graph GG satisfies E(G)≥2(n−α(G))\mathcal{E}(G)\ge 2(n-\alpha(G)). The conjecture was later recorded as Conjecture 543 in a survey by Aouchiche and Hansen.

Known results

  • Computational verification covered all graphs with at most 1010 vertices.
  • The inequality was known to hold for almost all graphs.
  • It followed for graphs satisfying Hoffman’s ratio bound, and in several other classes via fractional chromatic and theta-function bounds.

2026 proof

The paper “Energy and independence number” states that it proves the conjecture. Its argument uses a neighborhood-deletion inequality and induction, including n E(G)≥4m+∑v∈V(G)E(G−N[v])≥2n(n−α(G))n\,\mathcal{E}(G)\ge 4m+\sum_{v\in V(G)}\mathcal{E}(G-N[v])\ge 2n(n-\alpha(G)). This settles the inequality for all graphs.

Current status (as of August 2026): The conjecture is settled by an arXiv proof for every graph; no case remains open.

Sources

Solutions 0

No solutions have been posted yet.