A Counterexample to a Line-Graph Inertia Conjecture

Andrea Paone
Independent researcher, Italy
ORCID: 0009-0003-6194-948X
[email protected]

(Version 1.0 — 22 July 2026)

Abstract

We exhibit a connected simple graph $G$ on $14$ vertices and $16$ edges whose line graph has adjacency inertia

\operatorname{In}(L(G))=(9,0,7).

Consequently, $n^{+}(L(G))=9>8=n^{-}(L(G))+1$ , disproving Conjecture 4.12 of Akbari, Elphick, Kumar, Pragada and Tang. The certificate is finite and exact: the graph is specified by an edge list and graph6 encoding, the characteristic polynomial of $L(G)$ is given and factored over $\mathbb{Z}$ , and the signs of all roots are certified by rational isolating intervals. Reproducibility materials are available at doi:10.5281/zenodo.21499790.

Keywords: graph inertia; line graph; spectral graph theory; algebraic graph theory; counterexample.
MSC 2020: 05C50; 15A18.

1 Introduction

For a graph $H$ with adjacency matrix $A(H)$ , write

\operatorname{In}(H)=\bigl{(}n^{+}(H),n^{0}(H),n^{-}(H)\bigr{)},

where the entries count the positive, zero and negative eigenvalues of $A(H)$ with multiplicity. Akbari et al. [1] proposed the following statement as Conjecture 4.12:

n^{+}(L(G))\leq n^{-}(L(G))+1

(1)

for every connected graph $G$ , where $L(G)$ denotes the ordinary line graph.

We give an explicit connected simple graph for which (1) fails. A recent preprint of Chen and Li [2] refutes a different, global inertia conjecture from the same paper; it does not address Conjecture 4.12. To the best of our knowledge, the graph below is the first publicly reported counterexample to Conjecture 4.12. This priority statement is necessarily limited to publicly accessible and indexed work.

2 The graph

Let $G$ have vertex set $\{0,1,\ldots,13\}$ and edge set

	$\displaystyle E(G)=\{$	$\displaystyle(0,1),(1,2),(2,3),(3,4),(4,0),$
		$\displaystyle(5,6),(6,7),(7,8),(8,5),$
		$\displaystyle(9,10),(10,11),(11,12),(12,13),(13,9),$
		$\displaystyle(0,5),(6,9)\}.$

Thus $G$ consists of vertex-disjoint cycles $C_{5},C_{4},C_{5}$ joined in a chain by two bridges incident with adjacent vertices of the central $C_{4}$ . Its graph6 encoding is

\texttt{Mhe?GCD?\_?\_@?@?C\_}.

Figure 1: The connected graph

G

: two

5

-cycles joined through a central

4

-cycle. The bridges meet adjacent vertices of the central cycle.

The edge list has no loops or repeated unordered pairs, so $G$ is simple. The two bridge edges join the three cycles, so $G$ is connected. It has $14$ vertices and $16$ edges. Therefore $L(G)$ has $16$ vertices. Moreover,

|E(L(G))|=\sum_{v\in V(G)}\binom{\deg_{G}(v)}{2}=4\binom{3}{2}+10\binom{2}{2}=% 22.

3 Exact inertia certificate

Label the edges of $G$ in the order displayed above by $e_{0},\ldots,e_{15}$ . Construct $A=A(L(G))$ by setting $A_{ij}=1$ exactly when $e_{i}$ and $e_{j}$ share an endpoint. The complete matrix is included in Appendix A and in machine-readable form in the accompanying deposit.

A direct exact determinant computation gives

$\displaystyle p(x)$	$\displaystyle=\det(xI-A)$
	$\displaystyle=x^{16}-22x^{14}-8x^{13}+186x^{12}+108x^{11}-768x^{10}-500x^{9}$
	$\displaystyle\quad+1690x^{8}+956x^{7}-2110x^{6}-696x^{5}+1483x^{4}-8x^{3}$
	$\displaystyle\quad-456x^{2}+160x-16$
	$\displaystyle=(x-2)(x-1)(x+2)^{2}(x^{2}+x-1)^{2}$
	$\displaystyle\quad\cdot(x^{3}-2x^{2}-4x+1)$
	$\displaystyle\quad\cdot(x^{5}-x^{4}-6x^{3}+3x^{2}+7x-2).$	(2)

In particular, $p(0)=-16$ , so zero is not an eigenvalue.

Proposition 1.

The adjacency inertia of $L(G)$ is $(9,0,7)$ .

Proof.

The linear factors in (2) contribute two positive roots and two negative roots. The quadratic $x^{2}+x-1$ has one positive and one negative root; because it is squared, it contributes two roots of each sign.

For

f(x)=x^{3}-2x^{2}-4x+1,

we have

f(-2)=-7,\quad f(-1)=2,\quad f(0)=1,\quad f(1)=-4,\quad f(3)=-2,\quad f(4)=17.

Hence $f$ has roots in the three disjoint intervals $(-2,-1)$ , $(0,1)$ and $(3,4)$ . Since $f$ is cubic, these are all its roots, so it contributes one negative and two positive roots.

For

q(x)=x^{5}-x^{4}-6x^{3}+3x^{2}+7x-2,

the exact values

	$\displaystyle q(-2)=-4,\quad q(-3/2)=59/32,\quad q(-1)=-2,$
	$\displaystyle q(1/4)=-163/1024,\quad q(1/2)=47/32,$
	$\displaystyle q(1)=2,\quad q(3/2)=-79/32,$
	$\displaystyle q(5/2)=-29/32,\quad q(3)=46$

place roots in the five disjoint intervals

(-2,-3/2),\quad(-3/2,-1),\quad(1/4,1/2),\quad(1,3/2),\quad(5/2,3).

As $q$ has degree five, these are all its roots. Thus $q$ contributes two negative and three positive roots.

Summing the contributions gives

n^{+}(L(G))=2+2+2+3=9,\qquad n^{-}(L(G))=2+2+1+2=7,

and $n^{0}(L(G))=0$ . ∎

Theorem 1.

Conjecture 4.12 of Akbari et al. [1] is false.

Proof.

The graph $G$ is connected and simple, while Proposition 1 gives

n^{+}(L(G))=9>8=7+1=n^{-}(L(G))+1.

∎

4 Reproducibility and scope

The accompanying package contains the edge list, graph6 encoding, the complete adjacency matrix of $L(G)$ , a verification script, an exact JSON certificate and SHA-256 checksums. The script reconstructs $L(G)$ from the edge list and recomputes the characteristic polynomial, its factorization, determinant and exact root counts. Independent audit artifacts use additional exact routes, including unsigned-incidence identities and rational symmetric congruence.

The present note claims only the finite counterexample above. Computational evidence suggesting larger families is not used here and is not asserted as a theorem.

Tool-use statement.

Computer-assisted search and exact computation were used to discover and verify the graph. AI-assisted systems were used as programming and adversarial-review tools. All mathematical claims in this note are supported by explicit, independently reproducible finite certificates, and the author assumes full responsibility for the content.

License.

Appendix A Adjacency matrix of the line graph

With rows and columns ordered as $e_{0},\ldots,e_{15}$ , the adjacency matrix is

$\setcounter{MaxMatrixCols}{16}\begin{pmatrix}0&1&0&0&1&0&0&0&0&0&0&0&0&0&1&0\\ 1&0&1&0&0&0&0&0&0&0&0&0&0&0&0&0\\ 0&1&0&1&0&0&0&0&0&0&0&0&0&0&0&0\\ 0&0&1&0&1&0&0&0&0&0&0&0&0&0&0&0\\ 1&0&0&1&0&0&0&0&0&0&0&0&0&0&1&0\\ 0&0&0&0&0&0&1&0&1&0&0&0&0&0&1&1\\ 0&0&0&0&0&1&0&1&0&0&0&0&0&0&0&1\\ 0&0&0&0&0&0&1&0&1&0&0&0&0&0&0&0\\ 0&0&0&0&0&1&0&1&0&0&0&0&0&0&1&0\\ 0&0&0&0&0&0&0&0&0&0&1&0&0&1&0&1\\ 0&0&0&0&0&0&0&0&0&1&0&1&0&0&0&0\\ 0&0&0&0&0&0&0&0&0&0&1&0&1&0&0&0\\ 0&0&0&0&0&0&0&0&0&0&0&1&0&1&0&0\\ 0&0&0&0&0&0&0&0&0&1&0&0&1&0&0&1\\ 1&0&0&0&1&1&0&0&1&0&0&0&0&0&0&0\\ 0&0&0&0&0&1&1&0&0&1&0&0&0&1&0&0\end{pmatrix}$

References

[1] S. Akbari, C. Elphick, H. Kumar, S. Pragada and Q. Tang, A new conjecture on the inertia of graphs, Discrete Mathematics 349 (2026), no. 4, Article 114953. doi:10.1016/j.disc.2025.114953; arXiv:2508.01163v3.
[2] H. Chen and J. Li, Counterexamples to a conjecture on graph inertia, arXiv:2605.07196, 2026.