pith. sign in

arxiv: 2605.07196 · v1 · submitted 2026-05-08 · 🧮 math.CO

Counterexamples to a conjecture on graph inertia

Hongzhang Chen , Jianxi Li This is my paper

Pith reviewed 2026-05-11 02:23 UTC · model grok-4.3

classification 🧮 math.CO
keywords graph inertiaadjacency matrix eigenvaluescounterexamplesreduced graphsinertia tripleconjecture refutationspectral graph theory
0
0 comments X

The pith

A family of reduced graphs W_k for k at least 5 supplies explicit counterexamples to the conjectured inequality on the numbers of positive and negative eigenvalues.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper constructs an infinite family of reduced graphs W_k indexed by integers k of at least 5. Each member has adjacency-matrix inertia equal to binom(k,2) plus one positive eigenvalues, no zero eigenvalues, and exactly k minus one negative eigenvalues. This count directly violates the conjectured relation that twice the number of positive eigenvalues is at most the number of negative eigenvalues times one plus that same number. Removing a single vertex from the smallest case W_5 produces a reduced graph whose inertia is (10,0,4), thereby answering an open question posed in the paper that stated the original conjecture. The same family also falsifies a weaker inequality suggested in that earlier work.

Core claim

The authors construct a family of reduced graphs {W_k : k≥5} with In(W_k) = (binom(k,2)+1, 0, k-1), each of which violates the conjectured inequality 2n+(G) ≤ n-(G)(n-(G)+1). Deleting the vertex a1 from W_5 gives a reduced graph with inertia (10,0,4), answering a question raised in the same paper. The family also refutes a weaker inequality proposed there.

What carries the argument

The family of reduced graphs W_k whose adjacency matrices are shown to possess the inertia triple (binom(k,2)+1, 0, k-1) that exceeds the conjectured bound relating positive and negative eigenvalue counts.

If this is right

  • The conjectured inequality 2n+(G) ≤ n-(G)(n-(G)+1) fails to hold for all graphs.
  • A reduced graph with inertia (10,0,4) exists, obtained by deleting one vertex from W_5.
  • The weaker inequality proposed in the same source is also false.
  • Counterexamples of this form exist for every integer k at least 5.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The original bound may hold only after additional restrictions are imposed on the graphs under consideration.
  • The construction method could be examined for its ability to generate counterexamples to other proposed relations between inertia components.
  • The smallest-order reduced graphs that violate the bound can now be searched for systematically.

Load-bearing premise

The explicitly constructed graphs W_k possess exactly binom(k,2)+1 positive eigenvalues and k-1 negative eigenvalues in their adjacency matrices.

What would settle it

Explicit calculation of the full spectrum of the adjacency matrix of W_5 confirming whether it contains precisely eleven positive eigenvalues and four negative eigenvalues.

Figures

Figures reproduced from arXiv: 2605.07196 by Hongzhang Chen, Jianxi Li.

Figure 1
Figure 1. Figure 1: The graph W5. Set N = [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
read the original abstract

The inertia of a graph $G$ is $\operatorname{In}(G)=(n^+(G),n^0(G),n^-(G))$, where $n^+(G),\, n^0(G),\, n^-(G)$ are the numbers of positive, zero and negative eigenvalues of the adjacency matrix of $G$, respectively, counted with multiplicities. Akbari, Elphick, Kumar, Pragada and Tang [Discrete Math. 349 (2026) 114953] conjectured that every graph $G$ satisfies \[ 2n^+(G)\le n^-(G)(n^-(G)+1). \] In this note, we construct a family of reduced graphs $\{W_{k}:\,k\ge5\}$ with \[ \operatorname{In}(W_k) = \left(\binom{k}{2}+1,\ 0,\ k-1\right), \] each of which violates the conjectured inequality. We also observe that deleting the vertex $a_1$ from $W_5$ gives a reduced graph with inertia $(10,0,4)$, answering a question raised in the same paper. The family also refutes a weaker inequality proposed there.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 2 minor

Summary. The manuscript constructs an infinite family of reduced graphs {W_k : k ≥ 5} whose adjacency matrices have inertia (binom(k,2)+1, 0, k-1). These graphs violate the conjectured inequality 2n^+(G) ≤ n^-(G)(n^-(G)+1) proposed by Akbari et al. The paper also shows that deleting vertex a_1 from W_5 produces a reduced graph with inertia (10,0,4), answering a question from the same source, and refutes a weaker inequality stated there.

Significance. If the stated inertia values hold, the explicit combinatorial constructions supply a clean, infinite family of counterexamples that definitively refute the conjecture. The additional observation on W_5 directly resolves an open question raised in the source paper. Such concrete disproofs are valuable in spectral graph theory, where inertia bounds are often difficult to settle.

major comments (1)
  1. [§2] §2 (Construction of W_k and statement of inertia): The central claim that In(W_k) = (binom(k,2)+1, 0, k-1) for each k ≥ 5 is load-bearing for the counterexample, yet the manuscript provides only a sketch of the graph family and asserts the eigenvalue counts without a complete verification. A rigorous argument (e.g., via the characteristic polynomial, equitable partition, or direct computation of the inertia for the adjacency matrix) must be supplied; an error in the sign count or zero multiplicity for any single k would invalidate the refutation of 2n^+ ≤ n^-(n^-+1).
minor comments (2)
  1. [§2] The notation for the family {W_k} and the vertex labels (e.g., a_1) should be introduced with a clear diagram or adjacency-list description in the first paragraph of §2 to aid readability.
  2. [§3] The statement of the weaker inequality being refuted should be quoted verbatim from Akbari et al. for precision.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their positive evaluation of the significance of the counterexamples and for the detailed reading of the manuscript. We address the single major comment below.

read point-by-point responses

  1. Referee: [§2] §2 (Construction of W_k and statement of inertia): The central claim that In(W_k) = (binom(k,2)+1, 0, k-1) for each k ≥ 5 is load-bearing for the counterexample, yet the manuscript provides only a sketch of the graph family and asserts the eigenvalue counts without a complete verification. A rigorous argument (e.g., via the characteristic polynomial, equitable partition, or direct computation of the inertia for the adjacency matrix) must be supplied; an error in the sign count or zero multiplicity for any single k would invalidate the refutation of 2n^+ ≤ n^-(n^-+1).

    Authors: We agree that the inertia claim requires a fully rigorous and self-contained argument rather than a sketch, since it is the foundation of the counterexamples. In the revised manuscript we will expand §2 to include a complete proof. We will use the equitable partition induced by the natural vertex orbits of W_k (the distinguished vertex a_1 together with the symmetric classes of the a_i for i≥2 and the b_{ij} edges) to reduce the adjacency matrix to a quotient matrix of order O(k). The eigenvalues of this quotient matrix will be computed explicitly via its characteristic polynomial, after which the inertia of the original matrix follows from the equitable-partition theorem together with a direct count of the signs and the multiplicity of zero. We will also record explicit characteristic polynomials and inertia computations for the base cases k=5 and k=6 (verifiable by computer algebra) to illustrate the general pattern. This revision will make the refutation fully verifiable without altering any of the stated results. revision: yes

Circularity Check

0 steps flagged

Explicit construction of counterexamples with no circular derivation chain

full rationale

The paper's central contribution is the explicit construction of a family of graphs {W_k : k≥5} together with the direct statement of their inertia triple In(W_k) = (binom(k,2)+1, 0, k-1). This triple is obtained by defining the graphs and computing the spectrum of their adjacency matrices; it is not obtained by fitting parameters to data, renaming a known result, or invoking a self-citation that itself depends on the target claim. The conjecture being refuted originates from a different set of authors (Akbari et al.), so no self-citation load-bearing step exists. The secondary observation about deleting a vertex from W_5 is likewise a direct consequence of the same construction. No equation or step reduces to its own input by definition or by statistical forcing. The derivation is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The claim rests on the standard definition of graph inertia via the adjacency matrix spectrum and on the correctness of the authors' graph constructions; no free parameters or invented entities are introduced.

axioms (1)
  • standard math The inertia of a graph is the triple (n+, n0, n-) of positive, zero, and negative eigenvalues of its adjacency matrix counted with multiplicity.
    This is the standard definition in spectral graph theory invoked throughout the abstract.

pith-pipeline@v0.9.0 · 5515 in / 1166 out tokens · 48616 ms · 2026-05-11T02:23:48.799361+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

13 extracted references · 13 canonical work pages

  1. [1]

    Akbari, C

    S. Akbari, C. Elphick, H. Kumar, S. Pragada, Q. Tang, A new conjecture on the inertia of graphs, Discrete Math. 349 (2026) 114953

    work page 2026

  2. [2]

    Akbari, P

    S. Akbari, P. J. Cameron, G. B. Khosrovshahi, Ranks and signatures of adjacency matrices, URL:https://webspace.maths.qmul.ac.uk/p.j.cameron/preprints/ranksign.pdf

    work page

  3. [3]

    A. E. Brouwer, W. H. Haemers, Spectra of Graphs, Universitext, Springer, New York, 2012

    work page 2012

  4. [4]

    Cvetkovi´ c, M

    D. Cvetkovi´ c, M. Doob, H. Sachs, Spectra of Graphs: Theory and Application, Academic Press, New York, 1980

    work page 1980

  5. [5]

    Delsarte, J

    P. Delsarte, J. M. Goethals, J. J. Seidel, Spherical codes and designs, Geom. Dedic. 6 (1977) 363–388

    work page 1977

  6. [6]

    Y.-Z. Fan, L. Wang, Bounds for the positive and negative inertia index of a graph, Linear Algebra Appl. 522 (2017) 15–27

    work page 2017

  7. [7]

    Kotlov, L

    A. Kotlov, L. Lov´ asz, The rank and size of graphs, J. Graph Theory 23 (1996) 185–189

    work page 1996

  8. [8]

    H. Ma, W. Yang, S. Li, Positive and negative inertia index of a graph, Linear Algebra Appl. 438 (2013) 331–341

    work page 2013

  9. [9]

    J. J. Seidel, Strongly regular graphs, in: Surveys in Combinatorics, London Mathematical Society Lecture Note Series, vol. 38, Cambridge University Press, 1979, 157–180

    work page 1979

  10. [10]

    Torgaˇ sev, Graphs with exactly two negative eigenvalues, Math

    A. Torgaˇ sev, Graphs with exactly two negative eigenvalues, Math. Nachr. 122 (1985) 135–140

    work page 1985

  11. [11]

    Torgaˇ sev, On graphs with a fixed number of negative eigenvalues, Discrete Math

    A. Torgaˇ sev, On graphs with a fixed number of negative eigenvalues, Discrete Math. 57 (1985) 311–317

    work page 1985

  12. [12]

    Torgaˇ sev, Maximal canonical graphs with three negative eigenvalues, Publ

    A. Torgaˇ sev, Maximal canonical graphs with three negative eigenvalues, Publ. Inst. Math. (Belgr.) 45(59) (1989) 7–10

    work page 1989

  13. [13]

    Torgaˇ sev, On the numbers of positive and negative eigenvalues of a graph, Publ

    A. Torgaˇ sev, On the numbers of positive and negative eigenvalues of a graph, Publ. Inst. Math. (Belgr.) 51(65) (1992), 25–28. 9

    work page 1992