A Counterexample to a Line-Graph Inertia Conjecture

Akbari, Elphick, Kumar, Pragada, and Tang conjectured in Conjecture 4.12 of“A new conjecture on the inertia of graphs” (Discrete Mathematics 349 (2026),Article 114953; arXiv:2508.01163v3) that, for every connected graph G, its linegraph L(G) satisfies n_+(L(G)) <= n_-(L(G)) + 1, or equivalently s(L(G)) <= 1. The paper notes that connectedness is essential:without it, C5 disjoint-union C5 already gives a disconnected counterexample. We exhibit a connected simple graph G on 14 vertices and 16 edges, consistingof three cycles C5, C4, and C5 joined in a chain by two bridges attached toadjacent vertices of the central C4. Its line graph L(G) is connected and hasexact adjacency inertia In(L(G)) = (n_+, n_0, n_-) = (9, 0, 7). Therefore, n_+(L(G)) = 9 > 8 = n_-(L(G)) + 1, so G is a counterexample to Conjecture 4.12. The graph is specified by the graph6 string Mhe?GCD?_?_@?@?C_ and by the following edge description: C5: 0-1-2-3-4-0;C4: 5-6-7-8-5;C5: 9-10-11-12-13-9;bridges: 0-5 and 6-9. Moreover, det A(L(G)) = -16, so zero is not an eigenvalue. Over the integers,the characteristic polynomial of A(L(G)) factors as (x-2)(x-1)(x+2)^2(x^2+x-1)^2(x^3-2x^2-4x+1)(x^5-x^4-6x^3+3x^2+7x-2). The result is certified through multiple independent exact-arithmetic routes,including: (i) direct construction of the line graph, exact computation of thecharacteristic polynomial, and rational Sturm root-sign certificates; and(ii) an unsigned-incidence and signless-Laplacian route based on A(L(G)) = B^T B - 2I, together with exact rational-congruence certificates. The deposited materialsinclude the candidate graph, the complete line-graph adjacency matrix,machine-readable exact certificates, deterministic verification code,automated tests, and cryptographic checksums. This result concerns the line-graph conjecture, Conjecture 4.12, and is distinctfrom the counterexamples of Chen and Li (arXiv:2605.07196) to the generalgraph-inertia conjecture 2 n_+(G) <= n_-(G)(n_-(G)+1). To the best of the author’s knowledge, no prior public counterexample toConjecture 4.12 has appeared. This document is a preprint and has not undergoneformal peer review.