Line-Graph Signature Beyond the 2-Core:
Exact Counterexamples, Rooted Response, and Extremal
Constructions at Fixed Cyclomatic Number

Andrea Paone Marco Paone

(First version: 27 July 2026
Revised Version 1.2: 29 July 2026 — Preprint; not peer reviewed.)

Abstract

Let $L(G)$ be the line graph of a finite simple connected graph $G$ , and let $s(L(G))=n_{+}(L(G))-n_{-}(L(G))$ be the signature of its adjacency matrix. The conjecture $s(L(G))\leq 1$ has been refuted, and the signature is unbounded even over planar subcubic cactus graphs. We develop a $Q(G)-2I$ rooted-response and 2-core analysis of this phenomenon, organized by the cyclomatic number $c(G)$ . We prove an exact pendant-forest reduction onto a diagonally perturbed 2-core, a parity lemma making every rooted-tree response a well-defined odd/odd rational, a range-compatible attachment lemma for singular ports, and a rank-one criterion: a pendant leaf raises the signature exactly when the support response is below $-\tfrac{1}{2}$ . This mechanism gives exact, independently verified counterexamples to the monotone reduction $s(L(G))\leq\max(0,s(L(\operatorname{core}_{2}G)))$ . A ten-vertex witness with $c=4$ is the smallest found in the documented search, while global minimality, including exact order-nine exclusion, remains open; failure already occurs at $c=2$ .

Odd- $c$ amplifiers and a singular $C_{4}$ module for even $c$ give $f(c)\geq\lfloor(c+1)/2\rfloor$ . A short consequence of published tree Laplacian bounds, a spanning tree, the principal inclusion $L(T)\subseteq L(G)$ and interlacing gives $s(L(G))\leq c(G)$ . Therefore $\lfloor(c+1)/2\rfloor\leq f(c)\leq c$ , so $f(c)$ is finite and attained for every $c$ ; the coarse upper bound is not claimed as a new standalone theorem. The sharper bound $2s(L(G))\leq c(G)+1$ remains open. All load-bearing certificates use exact arithmetic. The package independently reproduces the exact census through order seven; order eight is an archived exact campaign result and order nine is screening only. In every tested domain, extremal hosts admit no response below $-\tfrac{1}{2}$ and absorb no pendant gain, while observed gains on non-extremal hosts fit inside their slack.

Keywords: line graph; inertia; signature; signless Laplacian; cyclomatic number; 2-core; Schur complement; rooted response.

2020 Mathematics Subject Classification: 05C50 (primary); 15A18 (secondary).

1 Introduction

The inertia of a graph $H$ is the triple $\operatorname{In}(H)=(n_{+}(H),n_{0}(H),n_{-}(H))$ of numbers of positive, zero and negative adjacency eigenvalues, and its signature is $s(H)=n_{+}(H)-n_{-}(H)$ . For line graphs, the classical identity $A(L(G))+2I=B^{\top}B$ (with $B$ the unoriented incidence matrix of $G$ ) forces $\lambda_{\min}(L(G))\geq-2$ and makes the spectrum of $L(G)$ an arithmetic shadow of the signless Laplacian $Q(G)=BB^{\top}$ ; the surrounding structure theory is classical [6].

Akbari, Elphick, Kumar, Pragada and Tang [1] recently proposed, alongside a global quadratic inertia bound later refuted by Chen and Li [5], the following line-graph conjecture (their Conjecture 4.12): for every connected graph $G$ ,

n_{+}(L(G))\ \leq\ n_{-}(L(G))+1,\qquad\text{i.e.}\qquad s(L(G))\leq 1.

(1)

They proved (1) for line graphs of trees and for the dense range $m\geq 2n-1$ , and verified it for all graphs of order at most nine.

In an earlier distinct preprint, publicly deposited on 22 July 2026, Paone gave an exact fourteen-vertex connected counterexample $G_{0}$ to (1) (three bridged cycles, $\operatorname{In}(L(G_{0}))=(9,0,7)$ ) [21]. A separate subsequent preprint, publicly deposited on 24 July 2026, established unboundedness and transfer principles: an explicit amplifier family $F_{k}$ of connected planar subcubic cactus graphs has $s(L(F_{k}))=k+1$ [22]. Francis and Uptain independently posted a related preprint on arXiv on 24 July 2026, presenting exact connected counterexamples and an unbounded chaining construction [11]. The Paone Version 2.0 and Francis–Uptain preprints therefore share the same public date; no intraday priority comparison is made here.

The parameter that survives these unboundedness results is the cyclomatic number $c(G)=|E(G)|-|V(G)|+1$ : the family $F_{k}$ has $c=2k+1$ , so its signature is exactly $\tfrac{c+1}{2}$ . The present paper is a distinct companion study, not a further version of either Paone preprint. It focuses on extremal signature at fixed cyclomatic number, rooted response, and the limitations of naïve 2-core reduction. Its contributions are:

1.

An exact reduction and its failure boundary. We prove an exact pendant-forest reduction (Proposition 3.6): the signature of $M(G)=Q(G)-2I$ equals a branch cost plus the signature of the 2-core matrix perturbed by an explicit diagonal. The reduction is unconditional: a parity lemma (Lemma 3.5) proves that every rooted-tree branch response is a well-defined odd/odd rational, so no branch can be silently skipped. The historically attractive shortcut — bounding the perturbed core by the unperturbed one, hence $s(L(G))\leq\max(0,s(L(\operatorname{core}_{2}G)))$ — is false. The ten-vertex counterexample of Theorem 4.1 is the smallest found in the documented search: a $K_{3,3}$ with one edge subdivided four times plus one pendant leaf. The failure occurs already at cyclomatic number two (Theorem 4.2).
2.

The response mechanism. A single local quantity governs these failures: the rooted response $g_{x}$ of $M$ at the support vertex. A pendant leaf raises $\operatorname{sig}M$ by $+1$ (net) exactly when $g_{x}<-\tfrac{1}{2}$ (Lemma 3.3), and the singular case is handled by a bordered-congruence lemma valid whenever the port equation $Ky=e$ is solvable (Lemma 3.1).
3.

A finite envelope at fixed $c$ . Writing $f(c)=\sup\{s(L(G)):c(G)=c\}$ , the released odd- $c$ amplifiers plus a new singular $C_{4}$ module for even $c$ prove $f(c)\geq\lfloor(c+1)/2\rfloor$ for every $c\geq 1$ (Theorem 5.2). A short corollary of published tree Laplacian results, a spanning tree and interlacing gives $s(L(G))\leq c(G)$ ; this coarse upper bound is not claimed as a new standalone theorem. Consequently $\lfloor(c+1)/2\rfloor\leq f(c)\leq c$ , and $f(c)$ is finite and attained. Two independently generated construction families attain the lower values; they coincide up to isomorphism for $c\leq 3$ and are verified non-isomorphic for $4\leq c\leq 13$ (no universal non-isomorphism statement beyond the verified range is claimed).
4.

The parameterized repair, as a conjecture. We conjecture $2\,s(L(G))\leq c(G)+1$ for all connected $G$ (Conjecture 5.3), equivalently $f(c)=\lfloor(c+1)/2\rfloor$ . The bound is reported exact-verified on every connected graph of order at most eight and screened without counterexample at order nine; this package independently reproduces the exhaustive exact census through order seven, while the order-eight result remains an archived campaign result.
5.

Protection. In every tested domain, hosts attaining the extremal signature admit no vertex of response below $-\tfrac{1}{2}$ and absorb no net pendant gain (Conjecture 6.1). This protects extremal cores; an implication to Conjecture 5.3 additionally requires a quantitative slack-absorption bound for non-extremal cores (Conjecture 6.2), which is stated separately and remains open.

Everything computational in this paper is exact: rational symmetric congruence, integer characteristic polynomials with certified root counts, and a third independent computer-algebra recomputation of the two central certificates. Floating point appears only in explicitly labelled screening statements. The provenance of the computations, including two independent blind exploration campaigns whose central witnesses turned out to be isomorphic, is documented in Appendix C.

2 Definitions and notation

All graphs are finite and simple; $G$ is connected unless stated otherwise. $A(G)$ is the adjacency matrix, $Q(G)=D(G)+A(G)$ the signless Laplacian, and

M(G)\ :=\ Q(G)-2I.

The line graph $L(G)$ has vertex set $E(G)$ , two edges adjacent when they share an endpoint. The cyclomatic number of a connected graph is $c(G)=m-n+1$ . The 2-core $\operatorname{core}_{2}G$ is the maximal subgraph of minimum degree at least two. For a symmetric real matrix $S$ we write $\operatorname{In}(S)=(n_{+},n_{0},n_{-})$ and $\operatorname{sig}(S)=n_{+}-n_{-}$ ; for a graph $H$ , $s(H):=\operatorname{sig}(A(H))$ . Congruent symmetric matrices have equal inertia (Sylvester; see [16]), and inertia is additive over Schur complements (Haynsworth [14]).

Definition 2.1 (Rooted response).

Let $H$ be a graph, $x\in V(H)$ , $M=M(H)$ , and $e_{x}$ the coordinate vector at $x$ . If $M$ is invertible, the response of $H$ at $x$ is $g_{x}=(M^{-1})_{xx}$ . If $M$ is singular but $e_{x}\in\operatorname{col}(M)$ , the generalized (range) response is $g_{x}=y_{x}$ for any solution $My=e_{x}$ ; this value does not depend on the chosen solution (Lemma 3.1). If $e_{x}\notin\operatorname{col}(M)$ the response is undefined and all statements below exclude that case explicitly.

Lemma 2.2 (Vertex-space identity; classical).

For every connected graph $G$ with $m\geq 1$ edges,

s(L(G))\ =\ \operatorname{sig}\bigl{(}M(G)\bigr{)}\ -\ c(G)\ +\ 1.

Proof.

$B^{\top}B=A(L(G))+2I$ and $BB^{\top}=Q(G)$ share their nonzero spectra; $\operatorname{rank}B=n-b$ , where $b=1$ if $G$ is bipartite and $0$ otherwise, is the standard incidence rank. Counting eigenvalues of $A(L(G))$ above, at and below $-2$ against eigenvalues of $Q$ above, at and below $2$ , and translating $m-n$ into $c-1$ , gives the display. (Full bookkeeping in Appendix A.) ∎

3 Exact attachment calculus

The calculus below packages classical ingredients into an exact $(\sigma,\rho)$ state formulation for $M(G)=Q(G)-2I$ : Schur/Haynsworth inertia additivity [14], range-compatible singular Schur complements [4], and the rooted attachment operations whose characteristic polynomials were computed by Schwenk [23] and by Godsil and McKay [12]. The graph operations themselves are classical; what is claimed as a contribution is the exact $Q-2I$ inertia and response packaging (including the exact 2-core reduction of Proposition 3.6), the odd/odd parity of Lemma 3.5, and the $-\tfrac{1}{2}$ threshold criterion of Lemma 3.3.

Lemma 3.1 (Singular attachment lemma).

Let $K$ be a symmetric $k\times k$ matrix, $e\in\mathbb{Q}^{k}$ , and suppose $Ky=e$ is solvable. Let $C$ be symmetric and $z$ any coupling vector, and set

S=\begin{pmatrix}K&ez^{\top}\\ ze^{\top}&C\end{pmatrix}.

Then $e^{\top}y$ is independent of the solution $y$ , and with $T=\begin{pmatrix}I&-yz^{\top}\\ 0&I\end{pmatrix}$ ,

T^{\top}S\,T\;=\;K\,\oplus\,\bigl{(}C-(e^{\top}y)\,zz^{\top}\bigr{)},\qquad% \text{hence}\qquad\operatorname{In}(S)=\operatorname{In}(K)+\operatorname{In}% \!\bigl{(}C-(e^{\top}y)\,zz^{\top}\bigr{)}.

Proof.

If $Ky=Ky^{\prime}=e$ then $y-y^{\prime}\in\ker K$ ; symmetry gives $e^{\top}(y-y^{\prime})=(Ky)^{\top}(y-y^{\prime})=y^{\top}K(y-y^{\prime})=0$ . The block multiplication uses only $Ky=e$ and $y^{\top}K=e^{\top}$ ; $T$ is unitriangular, so the congruence preserves inertia. ∎

Remark 3.2.

For invertible $K$ this is the classical Schur/Haynsworth computation with $e^{\top}y=e^{\top}K^{-1}e$ . Range-compatible generalized Schur complements for singular blocks are themselves classical (Carlson–Haynsworth–Markham [4]), and a closely related solvable-column cut-vertex congruence for graph adjacency matrices appears as Lemma 2.7 of Wang and Fan [26]. Lemma 3.1 is therefore not new singular Schur algebra: what is used here is the symmetric graph-port formulation with arbitrary coupling vector and response scalar $e^{\top}y$ , specialised to $Q-2I$ and applied to line-graph signature. The rooted-module lemma of the first author’s Version 2.0 [22] is the invertible-case ancestor.

Lemma 3.3 (Rank-one leaf-gain criterion).

Let $H$ be connected, $x\in V(H)$ , and let $G=H+\ell_{x}$ be $H$ with one pendant leaf at $x$ . Then

\operatorname{sig}M(G)\;=\;-1+\operatorname{sig}\bigl{(}M(H)+2e_{x}e_{x}^{\top% }\bigr{)},

and whenever the response $g_{x}$ of Definition 2.1 is defined,

\operatorname{sig}\bigl{(}M(H)+2e_{x}e_{x}^{\top}\bigr{)}-\operatorname{sig}M(% H)\;=\;\begin{cases}2&\text{if }g_{x}<-\tfrac{1}{2},\\ 1&\text{if }g_{x}=-\tfrac{1}{2},\\ 0&\text{if }g_{x}>-\tfrac{1}{2}.\end{cases}

Consequently $s(L(G))-s(L(H))\in\{-1,0,1\}$ , with $+1$ exactly when $g_{x}<-\tfrac{1}{2}$ (note $c(G)=c(H)$ ).

Proof.

The leaf contributes a new vertex $u$ of degree one: $M(G)$ is $M(H)$ with $M_{xx}$ increased by $1$ , bordered by the row/column $(e_{x};\,-1)$ . Pivoting on the $-1$ diagonal entry (a $1\times 1$ Schur step, Haynsworth) leaves $M(H)+2e_{x}e_{x}^{\top}$ at cost one negative eigenvalue: this is the first display. For the second, write the rank-one update as a bordered matrix and apply Lemma 3.1 with $K=M(H)$ , $e=e_{x}$ : the update $2e_{x}e_{x}^{\top}$ shifts the port block by $\bigl{(}\tfrac{1}{2}+g_{x}\bigr{)}$ -signed data; explicitly, congruence reduces the comparison to the sign of $1+2g_{x}$ . The three cases follow; the singular case uses the range response and the same computation on the solvable subspace. Appendix A gives the four-line matrix identity. The criterion was verified exactly on all 2,537 regular vertex cases (hosts with nonsingular $M(H)$ , including the boundary $g_{x}=-\tfrac{1}{2}$ ) across the connected min-degree-two hosts of order at most seven; the 214 hosts with singular $M(H)$ lie outside that criterion loop, and the singular-port congruence of Lemma 3.1 was tested separately (symbolic identities plus 300 exact singular instances, verifier RV-08). ∎

Remark 3.4 (Three distinct “gain” quantities).

Lemma 3.3 involves three deltas that must not be conflated. The net leaf gain on the vertex space is $\Delta_{M}(H,x)=\operatorname{sig}M(H+\ell_{x})-\operatorname{sig}M(H)\in\{-1,% 0,+1\}$ (the bordered extension adds one row and column). The rank-one update jump is $J(H,x)=\operatorname{sig}\bigl{(}M(H)+2e_{x}e_{x}^{\top}\bigr{)}-\operatorname% {sig}M(H)\in\{0,1,2\}$ (the matrix order does not change). The line-graph signature change is $s(L(H+\ell_{x}))-s(L(H))$ , which equals $\Delta_{M}(H,x)$ by Lemma 2.2, since $c$ is unchanged. They are related by $\Delta_{M}=J-1$ . Throughout this paper and its supplement, an unqualified “gain” always means the net quantity $\Delta_{M}$ (equivalently the line-graph change); the $\{0,1,2\}$ -valued quantity is always called the jump.

Lemma 3.5 (Rooted-tree invertibility and parity).

For every rooted tree $(T,r)$ the matrix $C_{T}=Q(T)-2I+e_{r}e_{r}^{\top}$ is nonsingular, and its response $\rho=(C_{T}^{-1})_{rr}$ is a rational number whose reduced numerator and denominator are both odd. In particular every rooted-tree branch response is defined.

Proof.

Induction on $|T|$ . Base: for the single vertex, $C_{T}=(0-2+1)=(-1)$ , so $C_{T}$ is nonsingular and $\rho=-1=-1/1$ , an odd/odd rational.

Step: let the root $r$ have $k\geq 1$ children, carrying the branch subtrees $(T_{i},r_{i})$ . In $C_{T}$ the diagonal entry at $r$ is $\deg_{T}(r)-2+1=k-1$ , and the block at each child subtree is exactly $C_{T_{i}}$ (the edge $rr_{i}$ raises the degree of $r_{i}$ by one, which is the $+e_{r_{i}}e_{r_{i}}^{\top}$ of the child’s own convention). By induction each $C_{T_{i}}$ is nonsingular with response $\rho_{i}=p_{i}/q_{i}$ in lowest terms, $p_{i}$ and $q_{i}$ both odd. Eliminating the child blocks at the root by Schur complement (Lemma 3.1, invertible case) reduces the root entry to

a\;=\;(k-1)-\sum_{i=1}^{k}\rho_{i}\;=\;\frac{N}{Q},\qquad Q=\prod_{i=1}^{k}q_{% i},\qquad N=(k-1)\,Q-\sum_{i=1}^{k}p_{i}\prod_{j\neq i}q_{j}.

Modulo $2$ : $Q\equiv 1$ and each $\prod_{j\neq i}q_{j}\equiv 1$ (products of odd numbers), and each $p_{i}\equiv 1$ , so

N\;\equiv\;(k-1)-k\;=\;-1\;\equiv\;1\pmod{2}.

Hence $N$ is odd, so $N\neq 0$ , so $a\neq 0$ : with all child blocks and the reduced root entry nonsingular, $C_{T}$ is nonsingular. Since $a$ is the $1\times 1$ Schur complement of the child blocks at the root, $(C_{T}^{-1})_{rr}=1/a$ (Haynsworth, invertible case of Lemma 3.1), so $\rho=1/a=Q/N$ ; any common factor of $Q$ and $N$ divides odd numbers, so the reduced numerator and denominator of $\rho$ remain odd. This closes the induction. ∎

The lemma was additionally verified exactly, by direct rational matrices against the recurrence, on all 141,083 rooted trees of order at most fifteen (no singular $C_{T}$ , no even reduced numerator or denominator; regression verifier RV-11).

Proposition 3.6 (Exact pendant-forest reduction).

Let $G$ be connected with nonempty 2-core $H=\operatorname{core}_{2}G$ , and for each core vertex $x$ let the pendant branches at $x$ be rooted trees $(T_{x,j},r_{x,j})$ with states $\sigma_{x,j}=\operatorname{sig}C_{T_{x,j}}$ and responses $\rho_{x,j}$ , where $C_{T}=Q(T)-2I+e_{r}e_{r}^{\top}$ . By Lemma 3.5 every branch response is defined. Then, with $\tau=\sum_{x,j}\sigma_{x,j}$ and $D_{xx}=\sum_{j}(1-\rho_{x,j})$ ,

\operatorname{sig}M(G)\;=\;\tau\;+\;\operatorname{sig}\bigl{(}M(H)+D\bigr{)}.

Proof.

Eliminate each branch by block congruence, innermost leaves first: each branch block is exactly $C_{T_{x,j}}$ (the $+e_{r}e_{r}^{\top}$ accounts for the edge into the core raising the root degree), nonsingular by Lemma 3.5, and Lemma 3.1 applied at each branch root replaces the branch by its signature cost $\sigma_{x,j}$ and the diagonal correction $(1-\rho_{x,j})$ at $x$ . Induction over branches gives the display; the recurrence for tree states (Proposition 3.7) computes each $(\sigma,\rho)$ in linear time. The formula was cross-checked exactly against direct matrices on all 1,205 rooted trees of order at most ten and on both central witnesses, and the state recurrence itself against direct matrices on all 141,083 rooted trees of order at most fifteen. ∎

Proposition 3.7 (One-port state recurrence).

For a rooted tree $(T,r)$ whose root has children with states $(\sigma_{i},\rho_{i})$ , the state of $(T,r)$ is given by $a=(k-1)-\sum_{i}\rho_{i}$ and

(\sigma,\rho)\;=\;\Bigl{(}\sum_{i}\sigma_{i}+\operatorname{sign}(a),\ 1/a\Bigr% {)},

with the single vertex having state $(-1,-1)$ ; by Lemma 3.5 the pivot $a$ is never zero when the children carry rooted-tree states, so the recurrence is total on rooted trees. (For generalized one-port states outside the rooted-tree state space — algebraic inputs that are not states of rooted trees — the value $a=0$ can occur; there the block is singular with $\sigma=\sum_{i}\sigma_{i}$ and the response is undefined: a composition that requires a response must stop or retain range/nullspace data instead of propagating a number.) Moreover $(\sigma,\rho)$ determines the signature effect of attaching the tree at any port with invertible block (sufficiency), and the exact state space is infinite: the star with $k$ leaves has state $\bigl{(}1-k,\;1/(2k-1)\bigr{)}$ .

Proof.

Schur elimination of the child blocks at the root (Lemma 3.1, invertible case) gives $a$ as the fully reduced root entry; sufficiency is Lemma 3.3 read with general modules. The star state follows by direct computation. Exhaustive cross-checking on all rooted trees through order ten (independent Beyer–Hedetniemi generation [3]) found no discrepancy with direct exact matrices. ∎

Remark 3.8 (Failure of the converses).

The invariant direction $\sigma=0\Rightarrow\rho=1$ holds for every rooted tree of order at most thirteen (exact); its converse $\rho=1\Rightarrow\sigma=0$ is false, first occurring in the verified rooted-tree census at order ten, where exactly three rooted trees have state $(-2,1)$ . The tentative law $\alpha\leq 2|\sigma|$ for $\alpha=1-\rho$ fails at order eleven (state $(-3,-21)$ , $\alpha=22$ ). Both facts are exact and were verified by independent enumeration.

4 Failure of naïve 2-core monotonicity

The reduction of Proposition 3.6 is exact. The tempting simplification — discard the diagonal $D$ and bound $s(L(G))$ by the unperturbed core — fails.

Theorem 4.1 (Exact counterexample, $c=4$ , ten vertices).

Let $H$ be $K_{3,3}$ with one edge subdivided into a path of length four (nine vertices, twelve edges, $c=4$ ), and let $G$ be $H$ plus one pendant leaf at the interior subdivision vertex $x$ adjacent to the $K_{3,3}$ side. Then, exactly,

\operatorname{In}(A(L(H)))=(6,0,6),\quad\operatorname{In}(A(L(G)))=(7,0,6),% \quad s(L(H))=0,\ \ s(L(G))=1,

so $s(L(G))>\max\bigl{(}0,s(L(\operatorname{core}_{2}G))\bigr{)}$ : the universal 2-core reduction is false. The mechanism is $g_{x}=-\tfrac{3}{2}<-\tfrac{1}{2}$ in Lemma 3.3. The principal quantity satisfies $2s(L(G))=2\leq 5=c+1$ .

Proof.

Finite exact computation, certified three independent ways (rational congruence; integer characteristic polynomial $(x-1)^{2}(x+2)^{3}(x^{8}-4x^{7}-8x^{6}+32x^{5}+25x^{4}-72x^{3}-32x^{2}+30x-4)$ with exact root counts; independent computer-algebra recomputation). Certificates and graph6 encodings are in Appendix B. Two independent blind exploration campaigns produced this witness in different encodings; the encodings are isomorphic, and the reconstruction from the verbal description above reproduces them exactly. ∎

Theorem 4.2 (The failure reaches $c=2$ ).

Let $H$ be the kayak-paddle-type dumbbell consisting of $C_{4}$ and $C_{5}$ joined by a path with two edges, and let $G$ be $H$ plus a pendant leaf at the connector midpoint $x$ (eleven vertices, $c=2$ ). Then $M(H)$ is singular, $e_{x}\in\operatorname{col}(M(H))$ with range response $g_{x}=-\tfrac{3}{4}$ , and exactly

s(L(H))=0,\qquad s(L(G))=1.

Hence the 2-core reduction, the uniform response bound $g\geq-\tfrac{1}{2}$ , and the support-rank diagonal-growth principle (a rank-one diagonal update can raise $\operatorname{sig}M$ by two) all fail already at cyclomatic number two. Again $2s(L(G))=2\leq 3=c+1$ .

Proof.

Exact certificates as in Theorem 4.1, with the singular port handled by Lemma 3.1; Appendix B. It is worth noting that kayak paddles $K(4,5,1)$ and $K(5,5,1)$ appear in [1] as equality cases of (1); the failure mechanism lives on closely related hosts. ∎

Remark 4.3 (Minimality, stated honestly).

The ten-vertex witness of Theorem 4.1 is the smallest found in the documented search. Negative domains behind it: every connected simple graph of order at most eight (12,113 isomorphism classes) was reported exact-negative by the archived campaign — of this, the order- $\leq 7$ stratum with at least one edge (995 graphs, orders two to seven) is independently re-verified and rerunnable from this package, while the order-eight stratum is an archived campaign result; every one-leaf attachment to every eight-vertex minimum-degree-two core (59,536 rooted updates, archived); the complete minimum-degree-two census $c\leq 4$ , $n\leq 10$ (archived). The complete order-nine traversal was floating-point screened with no positive retained; it is not an exact certificate. Global minimality, including exact order-nine exclusion, remains open.

5 Extremal constructions at fixed cyclomatic number

Definition 5.1.

$f(c)=\sup\{\,s(L(G)):G\text{ connected simple},\ c(G)=c\,\}$ .

A finite upper bound from published tree results.

We first record a short consequence of published results, not a new standalone theorem. If $T$ is a tree on $n\geq 2$ vertices, then $T$ is bipartite, so $Q(T)$ and its Laplacian have the same spectrum. Zhou, Zhou and Du [28, Theorems 4.1–4.2] prove that at least $\lceil n/2\rceil$ Laplacian eigenvalues of $T$ lie in $[0,2)$ , with equality exactly when $T$ has a perfect matching. For odd $n$ this already gives $\operatorname{sig}(Q(T)-2I)\leq-1$ . For even $n$ , the same conclusion is immediate unless equality holds; in the equality case Li, Shiu and Chang [17] prove that the $(n/2)$ -th largest Laplacian eigenvalue equals $2$ , again giving $\operatorname{sig}(Q(T)-2I)\leq-1$ . The vertex-space identity therefore yields

s(L(T))=\operatorname{sig}(Q(T)-2I)+1\leq 0.

The one-vertex tree has empty line graph and satisfies the same conclusion directly.

Now let $T$ be a spanning tree of a connected simple graph $G$ . The tree edges index a principal submatrix of $A(L(G))$ , namely $A(L(T))$ , of codimension

|E(G)|-|E(T)|=m-(n-1)=c(G).

Interlacing gives $n_{+}(L(G))\leq n_{+}(L(T))+c(G)$ and $n_{-}(L(G))\geq n_{-}(L(T))$ . Hence

s(L(G))\leq s(L(T))+c(G)\leq c(G).

Connected simple graphs of every cyclomatic number exist (for example, $K_{2,c+1}$ when $c\geq 1$ , and a tree when $c=0$ ). Since their signatures are integers bounded above by $c$ , the supremum defining $f(c)$ is a maximum. Combining this with Theorem 5.2 (and the tree case at $c=0$ ) gives, for every $c\geq 0$ ,

\left\lfloor\frac{c+1}{2}\right\rfloor\ \leq\ f(c)\ \leq\ c.

In particular, $f(c)$ is finite and attained for every $c$ .

Theorem 5.2 (Lower bound, every $c$ ).

For every integer $c\geq 1$ ,

f(c)\ \geq\ \Bigl{\lfloor}\tfrac{c+1}{2}\Bigr{\rfloor}.

Proof.

Odd $c=2k+1$ : the released amplifier family [22] has $\operatorname{In}(L(F_{k}))=(6k+3,0,5k+2)$ , hence $s=k+1=\frac{c+1}{2}$ , with an inductive block-congruence proof.

Even $c=2j$ : attach to $F_{j-1}$ (cyclomatic number $2j-1$ , signature $j$ ) a singular rooted $C_{4}$ module: a bridge from any host vertex to a four-cycle. In the edge ordering $(b,\,wx,\,xy,\,yz,\,zw)$ of Appendix A, the module’s line-graph block $K$ (five edges) has $\operatorname{In}(K)=(2,1,2)$ , and the explicit vector $y=(0,1,0,-1,0)^{\top}$ satisfies $Ky=e_{b}$ (column $w x$ minus column $y z$ ) and $e_{b}^{\top}y=0$ , so the even- $c$ step is visibly non-computational. Lemma 3.1 then gives $\operatorname{In}(L(G\star M))=\operatorname{In}(L(G))+(2,1,2)$ for every host: signature unchanged, cyclomatic number increased by one. Hence $f(2j)\geq j=\lfloor\frac{2j+1}{2}\rfloor$ . Appendix B records endpoint verifications for $c\leq 20$ (from the archived campaign table; rerunnable from this package for $c\leq 13$ ), and two independently generated families (alternating $\{4,5\}$ -block bridge chains, and the amplifier-plus-module family) attain the bound for every $c\leq 13$ ; the two families are isomorphic for $c\leq 3$ and verified non-isomorphic for $4\leq c\leq 13$ . Their relationship outside that range is not used anywhere in the proof. ∎

Conjecture 5.3 (Principal bound; parameterized repair of (1)).

For every connected simple graph $G$ ,

2\,s(L(G))\ \leq\ c(G)+1.

Equivalently (given Theorem 5.2): $f(c)=\lfloor(c+1)/2\rfloor$ for every $c\geq 1$ .

The exact evidence: no violation among all 12,113 connected simple graphs of order at most eight (exact; independently re-verified through order seven, the order-eight stratum being an archived campaign result); no violation in the complete minimum-degree-two census $c\leq 4$ , $n\leq 10$ (archived); none in the chorded-cycle family (12,474 rooted cases, archived), in 1,305 exact three-cycle chains (archived), in both construction families (rerunnable through $c=13$ ), nor in any pendant-attack configuration tested (Section 6). The complete order-nine traversal was screened without a violation (screening only). The conjecture remains open in both directions of proof effort; the failure of the monotone 2-core route removes the most direct known path to it.

6 The protection phenomenon

Call a minimum-degree-two host $H$ extremal if $2s(L(H))=c+1$ ( $c$ odd) or $2s(L(H))=c$ ( $c$ even).

Conjecture 6.1 (Protection).

An extremal host admits no vertex $x$ with response $g_{x}<-\tfrac{1}{2}$ ; equivalently, by Lemma 3.3, no single pendant leaf on an extremal host increases the line-graph signature. In its strong (multi-leaf) form: no pendant forest on an extremal host increases the line-graph signature. The strong form does not formally follow from the vertex-local form (simultaneous supports interact through Proposition 3.6) and is conjectured separately.

Protection controls extremal cores, but by itself it does not prove Conjecture 5.3 for non-extremal cores. The missing quantitative statement is stated separately:

Conjecture 6.2 (Quantitative slack absorption).

For every connected simple graph $G$ with nonempty 2-core $H$ ,

s(L(G))-s(L(H))\ \leq\ \Bigl{\lfloor}\tfrac{\,c(G)+1-2\,s(L(H))\,}{2}\Bigr{% \rfloor},

i.e. the net pendant-forest gain never exceeds the core’s available slack.

Since $c(G)=c(H)$ and signatures are integers, Conjecture 6.2 implies Conjecture 5.3 for every graph whose 2-core itself satisfies the principal bound, and its extremal case ( $2s(L(H))=c$ or $c+1$ ) is exactly the strong multi-leaf form of Conjecture 6.1. Conversely, Conjecture 6.1 alone does not yield Conjecture 5.3. Both statements are supported only in the declared finite domains below and remain open; the logical split is spelled out in Appendix A.

Exact evidence, declared domains (normalized counts). The adversarial scan (verifier RV-06) generates 730 host records: all connected minimum-degree-two graphs of order at most seven, the alternating $\{5,4\}$ -block bridge-chain family through $c=9$ , theta graphs $\Theta(a,b,c)$ with $a{+}b{+}c\leq 18$ , dumbbells $C_{a}\!-\!P_{t}\!-\!C_{b}$ ( $a,b\leq 8$ , $t\leq 3$ ), and subdivided $K_{4}$ and $K_{3,3}$ families. (The second construction family, amplifier-plus-module, is not part of this scan’s generator set.) After normalizing edge endpoints, the 730 records give 727 distinct labelled edge sets and 720 isomorphism classes; the scan runs on one representative per isomorphism class. Sixteen extremal records occur, giving 15 extremal labelled edge sets and 14 extremal isomorphism classes. The response scan (P1) runs on every extremal representative; the one-leaf scan (P2) runs on all 720 representatives; the two-leaf scan (P3) is capped at $n\leq 30$ , which excludes the three largest extremal classes (the bridge chains with $c=7,8,9$ : $n=32,36,41$ ), so exactly 11 extremal representatives receive it, for 1,400 tested two-leaf support pairs. Results: zero response violations, zero one-leaf gains and zero two-leaf gains on extremal representatives, and no principal-bound violation anywhere in the domain, while the 416 one-leaf gain events observed on non-extremal representatives all remain inside the slack $c+1-2s$ . Earlier campaign data agree: equality chains, all $c=2$ floor hosts to $n=13$ , and 2,563 exact boundary cases $g=-\tfrac{1}{2}$ with minimum found response $-\tfrac{29}{6}$ on non-extremal cores (archived campaign results, identified in the supplement’s campaign register). This is a bounded negative search, not a theorem; even- $c$ floor hosts of large order, defected equality hosts, and the excluded large extremal chains’ two-leaf behaviour remain untested.

7 Exact computations and reproducibility

Every load-bearing certificate reported as exact was evaluated without floating point. Two general exact routes were used: (i) rational symmetric congruence over $\mathbb{Q}$ (fraction arithmetic, no floating point); (ii) integer characteristic polynomials with certified real-root counts (square-free decomposition plus exact algebraic sign evaluation). A third, independent computer-algebra recomputation (exact eigenvalue signs) covers the two central witnesses only. Routes (i) and (ii) were implemented twice by independent agents and a third time for this manuscript; the compared exact certificates agree on every object subjected to both routes — not every object received every route, and the exact object-by-object route coverage is the supplement’s VERIFICATION_MATRIX.csv. The archived order-eight census and the $c=14,\dots,20$ endpoint table are not independently rerunnable from this package and are reported as archived campaign results; the same classification applies to the complete minimum-degree-two census $c\leq 4$ , $n\leq 10$ , the 59,536 one-leaf rooted updates, the 12,474 chorded-cycle cases and the 1,305 three-cycle chains. Every such archived campaign claim is listed, with its classification and the SHA-256 identity of its authority object, in the supplement’s CAMPAIGN_EVIDENCE_REGISTER.csv; none of them is presented as a self-contained exact certificate of this package. Floating point occurs only in the order-nine traversal, labelled as screening wherever cited. Graph generation used published, independent sources where possible (the Graph Atlas through order seven; Beyer–Hedetniemi rooted-tree generation [3]); enumeration counts were cross-checked against the standard sequences (e.g. 11,117 connected graphs of order eight; 141,083 rooted trees through order fifteen). Certificates, scripts, registers and the full verification matrix accompany this manuscript in its supplement. Appendix C details the provenance, including the two blind exploration campaigns and their reconciliation.

8 Relationship to prior work

•

Source conjecture and parallel refutations. (1) and its partial results (trees; $m\geq 2n-1$ ; small orders; equality cases including kayak paddles) are from [1]. Paone’s distinct Version 1.0 preprint [21] gives an exact connected counterexample; his separate Version 2.0 preprint [22] establishes unboundedness and transfer principles, including the odd- $c$ amplifiers used in Theorem 5.2. Francis and Uptain independently present exact connected counterexamples and an unbounded chaining construction [11]. The present Phase III paper is a distinct companion study rather than a new version of either Paone preprint; its specific focus is the structural mechanism, 2-core refutations, fixed- $c$ extremal constructions, parameterized conjecture and protection phenomenon. No corresponding Phase III-specific result is attributed to Francis–Uptain. Chen and Li [5] refuted the global quadratic conjecture of [1]; their work does not concern line graphs.
•

Signature bounds by cycle structure. Ma, Yang and Li [19] conjectured $-c_{3}(G)\leq s(G)\leq c_{5}(G)$ (cycle counts modulo four) and proved it for trees, unicyclic and bicyclic graphs; Wang and Fan [26] proved it for graphs that are line graphs. Those bounds are parameterized by cycle counts of the line graph; the bound conjectured here is parameterized by the cyclomatic number of the root graph and is of a different nature (it fails for no known graph and is tight on explicit families). An independent prior-art review completed on 27 July 2026 did not identify, within the searched English-language, DOI-indexed, arXiv-accessible and citation-linked literature, a result stating or directly implying the sharper $c(G)$ -parameterized form $2s(L(G))\leq c(G)+1$ (Appendix D); this is a bounded negative search, not a universal priority claim.
•

Multiplicity at $Q$ -eigenvalue $2$ and circuit rank. A cluster of results controls spectral counts of $Q$ at the same threshold $2$ , in cyclomatic parameters close to the one used here. Zhao and Yu [27] prove $m_{Q}(G,2)\leq c(G)+1$ for connected graphs with a perfect matching, with the equality case characterised; Li, Guo, Tian and Wang [18] prove $m_{Q}(G,2)\leq c_{2}(G)+1$ , and the Laplacian analogue, for every connected graph, where $c_{2}$ is the even cyclomatic number; Batal [2] bounds the multiplicities of even integer eigenvalues of $A$ , $L$ and $Q$ by circuit-rank expressions, which at $\lambda=2$ controls the nullity of $Q-2I$ . Earlier, Wang and Belardo [25] and Feng, Wang and Belardo [10] classified the graphs with at most two $Q$ -eigenvalues greater than (or at least) $2$ . These results are the nearest known neighbours of Conjecture 5.3 in matrix, threshold and parameter, and they absorb the multiplicity component of the picture: $m_{Q}(G,2)$ is exactly the nullity $n_{0}(Q-2I)$ . What they do not control is the signed quantity entering Lemma 2.2: the difference between the numbers of $Q$ -eigenvalues above and below $2$ . A multiplicity bound at $2$ , or a classification with a small number of eigenvalues above $2$ , constrains one coordinate of the inertia of $Q-2I$ without bounding $\operatorname{sig}(Q-2I)$ , and we found no elementary transformation from these results to $2\,s(L(G))\leq c(G)+1$ : they are near misses, not direct antecedents.
•

Trees and the coarse finite envelope. The tree stratum ( $c=0$ ) is covered by published work: nullity of $L(T)$ at most one [13], and the inertia of line graphs of trees is known [20]. More directly for the present purpose, the Laplacian count below $2$ proved by Zhou, Zhou and Du [28], together with the perfect-matching equality case of Li, Shiu and Chang [17], gives $s(L(T))\leq 0$ . A spanning tree and principal-submatrix interlacing then give $s(L(G))\leq c(G)$ . This coarse upper bound, and the resulting finiteness and attainment of $f(c)$ , are immediate consequences of published results and are not claimed as a new standalone theorem. They do not settle the sharper Conjecture 5.3.
•

Subdivision invariance. The signature part of the four-subdivision invariance used implicitly by our families is published: Lemma 2.1 of [19] contracts any internal path of four degree-two vertices with inertia change $(2,0,2)$ ; the integral (unimodular-congruence) refinement on line graphs is Theorem 7.2 of [22]. Neither is claimed as a contribution here. The distinction between the adjacency cokernel and the critical group is standard [24].
•

Rooted singularity, inverse diagonals and NSSDs. For an invertible symmetric matrix $K$ , the cofactor identity $(K^{-1})_{rr}=\det K[r]/\det K$ (with $K[r]$ the principal submatrix obtained by deleting row and column $r$ ) makes the vanishing of a diagonal entry of the inverse equivalent to the singularity of the corresponding vertex-deleted principal submatrix. That equivalence is classical and drives the NSSD literature: Farrugia, Gauci and Sciriha study weighted adjacency matrices with zero diagonal that are invertible while every one-vertex-deleted principal submatrix is singular [8, 9]. The rooted response used here is the same scalar $(M^{-1})_{xx}$ read through the same cofactor identity, but for the shifted signless Laplacian $M=Q-2I$ rather than a zero-diagonal adjacency matrix, with a sign/magnitude threshold at $-\tfrac{1}{2}$ rather than a vanishing condition, extended by a range response on singular ports, and applied through Lemma 3.3 to line-graph inertia. Within the documented search scope, none of the NSSD results was found to imply or to contradict the rank-one criterion or the attachment lemma; the overlap is the scalar condition’s algebraic form, not the theorems.
•

Rooted products and coalescence. Spectral formulas for attaching rooted graphs are classical: Schwenk’s characteristic-polynomial identities for coalescences [23] and the Godsil–McKay rooted product [12] compute characteristic polynomials of exactly the vertex-attachment operations used here, for the adjacency matrix. The congruence pattern itself is known: range-compatible singular Schur complements are classical [4], and Wang and Fan’s Lemma 2.7 [26] applies a solvable-column cut-vertex congruence of the same shape to graph adjacency matrices. What the bounded search through 27 July 2026 (Appendix D) did not locate is the full $Q-2I$ specialization used in this paper — the response scalar on a singular port together with the $-\tfrac{1}{2}$ threshold criterion for line-graph signature. No novelty is claimed for Schur complements, coalescence, characteristic-polynomial attachment identities, or the general congruence pattern; the one-port state recurrence (Proposition 3.7) is a $Q-2I$ state formulation derived from those classical rooted recurrences, not a new rooted-product theory.
•

Classical framework. The $\lambda_{\min}\geq-2$ theory is in [6], with later signature results for generalizations of line graphs in [15]. Inertia additivity is Haynsworth [14]; the range-compatible singular Schur-complement algebra is classical (Carlson–Haynsworth–Markham [4]). General inertia bounds for graphs in terms of matching number and cyclomatic number, for $A(G)$ rather than $A(L(G))$ , appear in [7].

9 Limitations and open problems

1.

Order-nine exactification. The order-nine negative for Conjecture 5.3 and for minimality of the ten-vertex witness is screening-only. A complete exact order-nine census (ideally with an independent canonical generator) would close both.
2.

Protection. Prove or refute Conjecture 6.1; the decisive question is whether an extremal host can carry a port of response below $-\tfrac{1}{2}$ . Large even- $c$ floor hosts are the first untested territory.
3.

Quantitative slack absorption. Prove or refute Conjecture 6.2; this, not protection alone, is what a reduction proof of Conjecture 5.3 requires (Appendix A).
4.

Sharp upper bound for $f(c)$ . The coarse bound $f(c)\leq c$ proves finiteness and attainment. What remains open is the sharp inequality $2s(L(G))\leq c(G)+1$ , equivalently $f(c)=\lfloor(c+1)/2\rfloor$ .
5.

Multi-port calculus. Extend Lemma 3.1 to a compositional calculus of generalized response matrices on singular multi-port modules (range/nullspace data included); classify crossing patterns.
6.

Kernel census. Suppressed kernels (minimum degree three multigraphs) satisfy $|V|\leq 2c-2$ ; the complete counts are $3$ , $15$ , $111$ for $c=2,3,4$ (verified by independent enumeration). Extending to $c=5$ would make the kernel route to Conjecture 5.3 concrete for small $c$ .
7.

Equality classification. Classify extremal graphs modulo four-subdivision and gain-neutral decorations; the released 256-class classification of three-cycle chains [22] is the seed.
8.

Algorithmics. The exact pipeline is FPT-shaped in $c$ (kernel plus rational port data), but the exact state space is infinite (Proposition 3.7), so any finite-state formulation must quotient by inequality-relevant behaviour; bit-complexity at fixed $c$ is open.

Concluding summary

Established in this manuscript, building on classical singular-Schur algebra and rooted-attachment methods: the exact pendant-forest reduction, the $Q-2I$ graph-port form of the singular attachment lemma, and the rank-one leaf-gain criterion. Established by combining the odd- $c$ amplifier family released in Version 2.0 [22] with the new even- $c$ singular $C_{4}$ module: the universal lower bound $f(c)\geq\lfloor(c+1)/2\rfloor$ . Established as a short consequence of published tree-spectrum results, a spanning tree and interlacing: $f(c)\leq c$ , so $f(c)$ is finite and attained for every $c$ . Refuted here (exactly): the monotone 2-core reduction, already at $c=2$ . Within the extremal-function envelope, only the sharper principal upper bound remains open: $2s(L(G))\leq c(G)+1$ (equivalently $f(c)=\lfloor(c+1)/2\rfloor$ ). Separate structural and computational questions are the protection conjecture, the quantitative slack-absorption conjecture, and global minimality of the ten-vertex witness (including exact order-nine exclusion).

Appendix A Proof details

A.1 Lemma 2.2

Let $B$ be the $n\times m$ unoriented incidence matrix. $B^{\top}B=A(L)+2I$ and $BB^{\top}=Q$ have equal nonzero spectra. Let $z_{Q}$ be the nullity of $Q$ ( $z_{Q}=1$ if $G$ is bipartite, $0$ otherwise), so that $\operatorname{rank}B=n-z_{Q}$ , and let $q_{+}$ , $q_{2}$ and $q_{-}^{\prime}$ count the eigenvalues of $Q$ greater than $2$ , equal to $2$ , and in the open interval $(0,2)$ , respectively. The zero eigenvalues of $Q$ are not part of the shared nonzero spectrum: the spectrum of $B^{\top}B$ consists of the nonzero eigenvalues of $Q$ together with $m-\operatorname{rank}B$ zeros. Since $A(L)=B^{\top}B-2I$ ,

n_{+}(L)=q_{+},\qquad n_{-}(L)=q_{-}^{\prime}+\bigl{(}m-\operatorname{rank}B% \bigr{)},\qquad n_{0}(L)=q_{2}.

Substituting $\operatorname{rank}B=n-z_{Q}$ ,

n_{-}(L)=q_{-}^{\prime}+\bigl{(}m-n+z_{Q}\bigr{)},\qquad\operatorname{sig}(M)=% q_{+}-q_{-}^{\prime}-z_{Q}

(in $M=Q-2I$ the $z_{Q}$ zero eigenvalues of $Q$ sit at $-2<0$ , so they are counted once, on the negative side of $M$ , and nowhere else). Subtracting,

s(L)=q_{+}-q_{-}^{\prime}-m+n-z_{Q}=\operatorname{sig}(M)-(m-n)=\operatorname{% sig}(M)-c+1,

the $z_{Q}$ terms cancelling identically, so no case split survives. The bookkeeping above keeps the zero spectrum of $Q$ out of $q_{-}^{\prime}$ throughout; a variant that counts all eigenvalues of $Q$ below $2$ in one number would count the zero eigenvalues twice for bipartite $G$ (already $K_{2}$ , with $\operatorname{spec}Q=\{2,0\}$ and $n_{-}(L(K_{2}))=0$ , refutes such a formula), which is why the interval $(0,2)$ is used from the start. The identity and this bookkeeping were checked exactly on $K_{2}$ , on nontrivial trees (including $P_{4}$ ), on odd cycles (including $C_{5}$ ), on all 995 connected Atlas graphs with at least one edge (orders two to seven; the edgeless $K_{1}$ lies outside the identity’s $m\geq 1$ hypothesis), and on every witness in this paper (regression verifier RV-11).

A.2 Lemma 3.3, second display

Consider the bordered matrix $S=\begin{pmatrix}-\tfrac{1}{2}&e_{x}^{\top}\\ e_{x}&M(H)\end{pmatrix}$ and compute its inertia twice. Pivoting on the invertible $(1,1)$ entry $-\tfrac{1}{2}$ (Haynsworth) gives $\operatorname{In}(S)=(0,0,1)+\operatorname{In}\bigl{(}M(H)+2e_{x}e_{x}^{\top}% \bigr{)}$ . Pivoting instead on the block $M(H)$ — literally when $M(H)$ is invertible, and through Lemma 3.1 (with $K=M(H)$ , $z=(1)$ , $e=e_{x}$ ) when it is singular with solvable port — gives $\operatorname{In}(S)=\operatorname{In}(M(H))+\operatorname{In}\bigl{(}-\tfrac{% 1}{2}-g_{x}\bigr{)}$ . Equating,

\operatorname{In}\bigl{(}M(H)+2e_{x}e_{x}^{\top}\bigr{)}-\operatorname{In}(M(H% ))=\operatorname{In}\bigl{(}-\tfrac{1}{2}-g_{x}\bigr{)}-(0,0,1)=\begin{cases}(% 1,0,-1)&g_{x}<-\tfrac{1}{2},\\ (0,1,-1)&g_{x}=-\tfrac{1}{2},\\ (0,0,0)&g_{x}>-\tfrac{1}{2},\end{cases}

which is exactly the claimed signature jump of $2$ , $1$ , $0$ . If $e_{x}\notin\operatorname{col}(M(H))$ the bordered matrix gains a hyperbolic pair and the jump is $1$ regardless; no witness in this paper needs that case.

A.3 What is still required to derive the principal bound

Proposition 3.6 separates two logically distinct needs. If the 2-core $H$ is extremal, Conjecture 6.1 would forbid a positive net pendant gain, so $2s(L(G))\leq 2s(L(H))\leq c+1$ on those graphs. If $H$ is not extremal, protection says nothing; one additionally needs the quantitative slack-absorption inequality of Conjecture 6.2, bounding the total pendant-forest gain by $\lfloor(c+1-2s(L(H)))/2\rfloor$ . The finite searches support both behaviours (every one of the 416 observed gain events fits inside the available slack), but neither statement is proved universally. Consequently no implication to Conjecture 5.3 is claimed in this paper.

A.4 Even- $c$ module of Theorem 5.2

The module $M$ is a bridge $b$ from the host vertex $v$ to a $C_{4}$ . Its line-graph block on the five module edges, ordered $(b,\,wx,\,xy,\,yz,\,zw)$ with the $C_{4}$ on $w, x, y, z$ and $b=vw$ :

K=\begin{pmatrix}0&1&0&0&1\\ 1&0&1&0&1\\ 0&1&0&1&0\\ 0&0&1&0&1\\ 1&1&0&1&0\end{pmatrix}\quad\text{(up to the stated ordering)},\qquad% \operatorname{In}(K)=(2,1,2),

$Ky=e_{b}$ solvable, $e_{b}^{\top}y=0$ (exact certificates in the supplement). The coupling of the module to $L(H)$ is exactly $e_{b}z^{\top}$ with $z$ the indicator of host edges at $v$ , so Lemma 3.1 gives $\operatorname{In}(L(H\star M))=\operatorname{In}(L(H))+(2,1,2)$ : signature preserved, one cycle and five edges added. Composing with the odd- $c$ amplifiers yields every even $c$ .

Appendix B Counterexample certificates

All encodings are standard graph6.

W1: the common ten-vertex witness (Theorem 4.1)

host $H$	HBzc?CP (isomorphic encoding: HsX_WCP)
graph $G$	IBzc?CP?_ (isomorphic: IsX_WCP?O)
parameters	$n(G)=10$ , $m(G)=13$ , $c=4$ , leaf support $x$ = subdivision vertex
inertias	$\operatorname{In}(L(H))=(6,0,6)$ , $\operatorname{In}(L(G))=(7,0,6)$ ; $\operatorname{In}(M(H))=(6,0,3)$ , $\operatorname{In}(M(G))=(7,0,3)$
response	$g_{x}=-\tfrac{3}{2}$ (regular); $\operatorname{In}(M(H)+2e_{x}e_{x}^{\top})=(7,0,2)$

Characteristic polynomial of $A(L(G))$ :

(x-1)^{2}(x+2)^{3}\bigl{(}x^{8}-4x^{7}-8x^{6}+32x^{5}+25x^{4}-72x^{3}-32x^{2}+% 30x-4\bigr{)}.

W2: the $c=2$ witness (Theorem 4.2)

host $H$	Il?GGCHa? ( $C_{4}$ – $P_{2}$ – $C_{5}$ dumbbell, $n=10$ , $m=11$ , $c=2$ )
graph $G$	Jl?GGCHa??_ (leaf at connector midpoint)
inertias	$\operatorname{In}(L(H))=(5,1,5)$ , $\operatorname{In}(L(G))=(6,1,5)$ ; $\operatorname{In}(M(H))=(5,1,4)$ , $\operatorname{In}(M(G))=(6,1,4)$
response	$\det M(H)=0$ ; range response $g_{x}=-\tfrac{3}{4}$

Characteristic polynomial of $A(L(G))$ :

x(x+2)(x^{2}+x-1)\bigl{(}x^{8}-3x^{7}-8x^{6}+23x^{5}+21x^{4}-52x^{3}-16x^{2}+3% 4x-4\bigr{)}.

W3: seed certificate (released, [21, 22])

$C_{5}$ – $C_{4}$ – $C_{5}$ bridge chain: $n=14$ , $m=16$ , $c=3$ , $\operatorname{In}(L)=(9,0,7)$ , $s=2$ : the released refutation of (1) (originating in Version 1.0 [21]), reproduced from scratch in this workstream.

Extremal witnesses

Both families ( $\{4,5\}$ -block bridge chains; amplifiers plus singular $C_{4}$ modules) attain $s=\lfloor(c+1)/2\rfloor$ for all $1\leq c\leq 13$ exactly and rerunnably from this package; the second family’s $c=14,\dots,20$ endpoints come from the archived campaign table (provenance and hash recorded in the supplement) and are not independently rerunnable here. Tables, encodings and scripts are in the supplement.

Rooted-state certificates

First converse failures in the verified rooted-tree census: exactly three rooted trees of order ten with state $(-2,1)$ . The $\alpha$ -law failure: the order-eleven rooted tree $(((),()),((),((),((),()))))$ with state $(-3,-21)$ , $\alpha=22$ .

Appendix C Computational methods and provenance

Two independent, mutually blind exploration campaigns (July 2026) attacked the same frozen programme from the same released baseline [22]: one produced the order-eight exact census, the chorded-cycle and structured searches, the rooted census through order fifteen and the even- $c$ module; the other produced the kernel censuses, the $\{4,5\}$ -chain family, the protection scans and the $c=2$ witness. Their central 2-core counterexamples, found independently and encoded differently, are isomorphic. Both campaigns were archived byte-exactly with SHA-256 custody records. A third, separate verification workstream re-implemented the central exact arithmetic from scratch (two general routes plus a computer-algebra recomputation of the two central witnesses), re-derived the load-bearing certificates from verbal descriptions alone, re-enumerated rooted trees and kernels with independent generators, and re-verified the construction families through the declared rerunnable ranges. The order-eight census and the $c=14,\dots,20$ endpoint table remain declared reproducibility gaps of this package; the complete computation register and the object-by-object route table accompany the supplement. Screening-only statements are labelled as such wherever they occur.

Appendix D Search and prior-art scope

The prior-art review behind Section 8 covered, up to the cut-off of 26 July 2026: arXiv, indexed web search (multiple queries), Semantic Scholar forward citations of [1], the released project record, the full texts of [1], [5], [26] and [8], and the publisher metadata and abstracts of [9], [23] and [12] (all DOI metadata verified against the registration agencies). Subscription databases (zbMATH, MathSciNet), Crossref/OpenAlex sweeps, publisher full texts behind paywalls, and non-English literature were not systematically covered. All negative statements attributed to that earlier review are bounded by that scope. The paragraph above is a historical record of the earlier internal review and is intentionally preserved.

The independent OBL-R7 prior-art review, completed on 27 July 2026, subsequently extended the operational search cut-off through 27 July 2026. It covered arXiv full texts, publisher and DOI records, indexed web search, Semantic Scholar (including all indexed forward citations of [26]), OpenAlex exact records, zbMATH Open indexed records, multilingual indexed queries and correction/erratum status checks, and it added the near-art cluster now cited in Section 8 ([27, 18, 2, 25, 10]). Within the searched English-language, DOI-indexed, arXiv-accessible and citation-linked literature, that review did not identify a result stating or directly implying the sharper conjectural bound $2s(L(G))\leq c(G)+1$ . The later targeted correction review did identify the published tree-spectrum route [28, 17] that immediately gives the coarser $s(L(G))\leq c(G)$ after spanning-tree interlacing; no novelty is claimed for that consequence. The negative search statement is bounded and applies only to the sharper conjecture, not to finiteness. Its principal declared limits: authenticated MathSciNet was not available; direct Google Scholar access was not available; several full texts remain behind paywalls; and multilingual coverage relied on indexed web queries rather than exhaustive specialist databases.

A final targeted bibliographic check on 28 July 2026 directly verified the arXiv record and Version 1 full text of Francis and Uptain [11]. Their preprint was submitted on 24 July 2026 and contains exact connected counterexamples together with an unbounded chaining construction. It is cited here as independent parallel work on refutation and unboundedness; the checked text does not state the fixed-cyclomatic, rooted-response, or 2-core-reduction results developed in the present companion paper. No absolute or intraday priority claim is made.

Author Information and Correspondence

Andrea Paone
Independent Researcher.
ORCID: 0009-0003-6194-948X.
Email: [email protected].
Corresponding author.

Marco Paone
Independent Researcher.
ORCID: 0009-0001-6792-879X.
Email: [email protected].

Author contributions

Andrea Paone and Marco Paone contributed equally to this work.

Author approval and accountability

Both authors reviewed and approved the final manuscript and accept accountability for their contributions.

Funding

The authors received no external funding for this work.

Competing interests

The authors declare no competing interests.

Declaration of generative AI and AI-assisted technologies in the manuscript preparation process

During the research and preparation of this work, the authors used large-language-model services from the GPT-5.6 family (High and Pro configurations) and the Claude family (Opus and Fable 5 models), together with AI-assisted coding tools driven by those models, to support exploratory analysis, code development and checking, literature triage, internal pre-submission critique, and manuscript editing.

All mathematical statements, proofs, citations, exact certificates, and computational results incorporated into the manuscript were reviewed and checked by the authors against the relevant primary sources and reproducible materials. The authors revised and approved the final manuscript and take full responsibility for its content. Generative-AI systems were not credited as authors, were not treated as sources of mathematical or scientific authority, and did not make autonomous publication or research decisions.

Data, code and supplementary materials

The verification code, exact certificates, data tables, canonical outputs and scientific registers supporting this work are publicly available in the accompanying reproducibility package. All first-party material in that package is released under the Creative Commons Attribution 4.0 International licence (CC BY 4.0). Third-party software dependencies are not included and retain their own licences.

Licence

This manuscript and all first-party materials in the accompanying reproducibility package are licensed under the Creative Commons Attribution 4.0 International licence (CC BY 4.0), https://creativecommons.org/licenses/by/4.0/. This includes the LaTeX source, verification software, exact certificates, data tables, canonical outputs and scientific registers. Third-party software dependencies are not included and retain their own licences.

References

[1] S. Akbari, C. Elphick, H. Kumar, S. Pragada, and Q. Tang (2026) A new conjecture on the inertia of graphs. Discrete Mathematics 349, pp. 114953. Note: arXiv:2508.01163 External Links: Document Cited by: Appendix D, §1, §4, 1st item.
[2] A. Batal (2026) Bounding the multiplicities of eigenvalues of graph matrices in terms of circuit rank. Hacettepe Journal of Mathematics and Statistics 55 (2), pp. 502–511. Note: arXiv:2212.11643 External Links: Document Cited by: Appendix D, 3rd item.
[3] T. Beyer and S. M. Hedetniemi (1980) Constant time generation of rooted trees. SIAM Journal on Computing 9 (4), pp. 706–712. External Links: Document Cited by: §3, §7.
[4] D. Carlson, E. V. Haynsworth, and T. Markham (1974) A generalization of the Schur complement by means of the Moore–Penrose inverse. SIAM Journal on Applied Mathematics 26 (1), pp. 169–175. External Links: Document Cited by: Remark 3.2, §3, 7th item, 8th item.
[5] H. Chen and J. Li (2026) Counterexamples to a conjecture on graph inertia. Note: arXiv:2605.07196, preprint Cited by: Appendix D, §1, 1st item.
[6] D. Cvetković, P. Rowlinson, and S. Simić (2004) Spectral generalizations of line graphs: on graphs with least eigenvalue $-2$ . London Mathematical Society Lecture Note Series, Vol. 314, Cambridge University Press. Cited by: §1, 8th item.
[7] Y. Fan and L. Wang (2017) Bounds for the positive and negative inertia index of a graph. Linear Algebra and its Applications 522, pp. 15–27. External Links: Document Cited by: 8th item.
[8] A. Farrugia, J. B. Gauci, and I. Sciriha (2013) On the inverse of the adjacency matrix of a graph. Special Matrices 1, pp. 28–41. External Links: Document Cited by: Appendix D, 6th item.
[9] A. Farrugia, J. B. Gauci, and I. Sciriha (2016) Non-Singular graphs with a Singular Deck. Discrete Applied Mathematics 202, pp. 50–57. External Links: Document Cited by: Appendix D, 6th item.
[10] X. Feng, J. Wang, and F. Belardo (2018) Spectral characterizations of graphs with at most two (signless) Laplacian eigenvalues greater than 2. Ars Combinatoria 139, pp. 43–54. Cited by: Appendix D, 3rd item.
[11] L. Francis and T. Uptain (2026) The Signature of Connected Line Graphs Is Unbounded. Note: arXiv preprintarXiv:2607.22874, submitted 24 July 2026 External Links: Link Cited by: Appendix D, §1, 1st item.
[12] C. D. Godsil and B. D. McKay (1978) A new graph product and its spectrum. Bulletin of the Australian Mathematical Society 18 (1), pp. 21–28. External Links: Document Cited by: Appendix D, §3, 7th item.
[13] I. Gutman and I. Sciriha (2001) On the nullity of line graphs of trees. Discrete Mathematics 232, pp. 35–45. External Links: Document Cited by: 4th item.
[14] E. V. Haynsworth (1968) Determination of the inertia of a partitioned Hermitian matrix. Linear Algebra and its Applications 1, pp. 73–81. External Links: Document Cited by: §2, §3, 8th item.
[15] C. He and H. Shan (2019) The signature of two generalizations of line graphs. Linear Algebra and its Applications 575, pp. 159–173. External Links: Document Cited by: 8th item.
[16] R. A. Horn and C. R. Johnson (2013) Matrix analysis. 2 edition, Cambridge University Press. Cited by: §2.
[17] J. Li, W. C. Shiu, and A. Chang (2010) On the $k$ th Laplacian eigenvalues of trees with perfect matchings. Linear Algebra and its Applications 432 (4), pp. 1036–1041. External Links: Document Cited by: Appendix D, §5, 4th item.
[18] X. Li, J. Guo, F. Tian, and Z. Wang (2026) Improved upper bound of multiplicity of (signless) Laplacian eigenvalue two. Linear Algebra and its Applications 728, pp. 419–434. External Links: Document Cited by: Appendix D, 3rd item.
[19] H. Ma, W. Yang, and S. Li (2013) Positive and negative inertia index of a graph. Linear Algebra and its Applications 438, pp. 331–341. External Links: Document Cited by: 2nd item, 5th item.
[20] X. Ma, D. Wong, and M. Zhu (2013) The positive and the negative inertia index of line graphs of trees. Linear Algebra and its Applications 439 (10), pp. 3120–3128. External Links: Document Cited by: 4th item.
[21] A. Paone (2026) A Counterexample to a Line-Graph Inertia Conjecture. Note: ZenodoVersion 1.0 research version External Links: Document Cited by: Appendix B, Appendix B, §1, 1st item.
[22] A. Paone (2026) Unbounded Signature of Line Graphs: Counterexamples and Transfer Principles. Note: ZenodoVersion 2.0 research version, released 24 July 2026 External Links: Document Cited by: Appendix B, Appendix C, §1, Remark 3.2, §5, 1st item, 5th item, item 7, §9.
[23] A. J. Schwenk (1974) Computing the characteristic polynomial of a graph. In Graphs and Combinatorics, Lecture Notes in Mathematics, Vol. 406, pp. 153–172. External Links: Document Cited by: Appendix D, §3, 7th item.
[24] R. P. Stanley (2016) Smith normal form in combinatorics. Journal of Combinatorial Theory, Series A 144, pp. 476–495. External Links: Document Cited by: 5th item.
[25] J. Wang and F. Belardo (2013) Signless Laplacian eigenvalues and circumference of graphs. Discrete Applied Mathematics 161 (10-11), pp. 1610–1617. External Links: Document Cited by: Appendix D, 3rd item.
[26] L. Wang and Y. Fan (2014) The signature of line graphs and power trees. Linear Algebra and its Applications 448, pp. 264–273. Note: arXiv:1310.1003 External Links: Document Cited by: Appendix D, Appendix D, Remark 3.2, 2nd item, 7th item.
[27] J. Zhao and X. Yu (2025) Multiplicity of signless Laplacian eigenvalue 2 of a connected graph with a perfect matching. Discrete Applied Mathematics 361, pp. 480–486. External Links: Document Cited by: Appendix D, 3rd item.
[28] L. Zhou, B. Zhou, and Z. Du (2015) On the number of Laplacian eigenvalues of trees smaller than two. Taiwanese Journal of Mathematics 19 (1), pp. 65–75. External Links: Document Cited by: Appendix D, §5, 4th item.

Line-Graph Signature Beyond the 2-Core: Exact Counterexamples, Rooted Response, and Extremal Constructions at Fixed Cyclomatic Number

Abstract

1 Introduction

2 Definitions and notation

Definition 2.1 (Rooted response).

Lemma 2.2 (Vertex-space identity; classical).

Proof.

3 Exact attachment calculus

Lemma 3.1 (Singular attachment lemma).

Proof.

Remark 3.2.

Lemma 3.3 (Rank-one leaf-gain criterion).

Proof.

Remark 3.4 (Three distinct “gain” quantities).

Lemma 3.5 (Rooted-tree invertibility and parity).

Proof.

Proposition 3.6 (Exact pendant-forest reduction).

Proof.

Proposition 3.7 (One-port state recurrence).

Proof.

Remark 3.8 (Failure of the converses).

4 Failure of naïve 2-core monotonicity

Theorem 4.1 (Exact counterexample, c=4, ten vertices).

Proof.

Theorem 4.2 (The failure reaches c=2).

Proof.

Remark 4.3 (Minimality, stated honestly).

5 Extremal constructions at fixed cyclomatic number

Definition 5.1.

A finite upper bound from published tree results.

Theorem 5.2 (Lower bound, every c).

Proof.

Conjecture 5.3 (Principal bound; parameterized repair of (1)).

6 The protection phenomenon

Conjecture 6.1 (Protection).

Conjecture 6.2 (Quantitative slack absorption).

7 Exact computations and reproducibility

8 Relationship to prior work

9 Limitations and open problems

Concluding summary

Appendix A Proof details

A.1 Lemma 2.2

A.2 Lemma 3.3, second display

A.3 What is still required to derive the principal bound

A.4 Even-c module of Theorem 5.2

Appendix B Counterexample certificates

W1: the common ten-vertex witness (Theorem 4.1)

W2: the c=2 witness (Theorem 4.2)

W3: seed certificate (released, [21, 22])

Extremal witnesses

Rooted-state certificates

Appendix C Computational methods and provenance

Appendix D Search and prior-art scope

Author Information and Correspondence

Author contributions

Author approval and accountability

Funding

Competing interests

Declaration of generative AI and AI-assisted technologies in the manuscript preparation process

Data, code and supplementary materials

Licence

References

Line-Graph Signature Beyond the 2-Core:
Exact Counterexamples, Rooted Response, and Extremal
Constructions at Fixed Cyclomatic Number

Theorem 4.1 (Exact counterexample, $c=4$ , ten vertices).

Theorem 4.2 (The failure reaches $c=2$ ).

Theorem 5.2 (Lower bound, every $c$ ).

A.4 Even- $c$ module of Theorem 5.2

W2: the $c=2$ witness (Theorem 4.2)