Line-Graph Signature Beyond the 2-Core:
Counterexamples, Pendant Attachments, and Bounds
at Fixed Cyclomatic Number

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

(Version 1.3 - 30 July 2026)

Abstract

Let $L(G)$ be the line graph of a finite simple connected graph $G$ , and let $s(L(G))$ denote the signature of its adjacency matrix. The conjecture $s(L(G))\leq 1$ is false, and the signature is unbounded when the cyclomatic number is allowed to grow. This paper studies what remains true when the cyclomatic number $c(G)$ is fixed and explains how trees attached to the 2-core affect the signature.

The main tool is an exact reduction for $M(G)=Q(G)-2I$ . Each pendant tree contributes an inertia term and a diagonal correction on the 2-core. A single attached leaf increases $s(L(G))$ precisely when a scalar response at its attachment vertex is smaller than $-\tfrac{1}{2}$ . This criterion produces exact counterexamples to the inequality $s(L(G))\leq\max\{0,s(L(\operatorname{core}_{2}G))\}$ , including one with cyclomatic number two.

For

f(c)=\max\{s(L(G)):G\text{ connected and }c(G)=c\},

explicit constructions give $f(c)\geq\lfloor(c+1)/2\rfloor$ , while published results on tree Laplacian spectra and interlacing imply $f(c)\leq c$ . Thus $f(c)$ is finite and attained for every $c$ . The sharper inequality $2s(L(G))\leq c(G)+1$ remains open. Exact computations support it through order eight; the accompanying code independently reproduces the census through order seven, while the order-nine computation is numerical screening only.

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

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

Revision note, 30 July 2026. Version 1.3 revises the presentation and grammar for clarity and adds figures illustrating the main constructions. The mathematical statements and computational results are unchanged.

1 Introduction

For a graph $H$ , let $\operatorname{In}(H)=(n_{+}(H),n_{0}(H),n_{-}(H))$ be the inertia of its adjacency matrix and let $s(H)=n_{+}(H)-n_{-}(H)$ be its signature. If $G$ is a connected graph with unoriented incidence matrix $B$ , then

A(L(G))+2I=B^{\top}B,\qquad Q(G)=BB^{\top},

where $Q(G)$ is the signless Laplacian. The nonzero spectra of $B^{\top}B$ and $BB^{\top}$ agree, so the signature of the line graph can be studied on the vertex space of $G$ through the shifted matrix

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

This elementary identity is the starting point of the paper.

Akbari, Elphick, Kumar, Pragada and Tang conjectured that

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

(1)

for every connected graph $G$ [1]. They proved the inequality for line graphs of trees and in a dense range, and verified it for small graphs. Exact connected counterexamples were subsequently given by Paone [21], and unbounded families, including planar subcubic cactus graphs, were obtained by Paone [22]; Francis and Uptain independently obtained another unbounded construction [11]. Chen and Li [5] refuted a different, global inertia conjecture from the same source paper.

Unboundedness leaves a natural parameterized question. The cyclomatic number

c(G)=|E(G)|-|V(G)|+1

counts the number of independent cycles of a connected graph. The known unbounded families increase their signature by increasing $c(G)$ . This suggests asking how large $s(L(G))$ can be when $c(G)$ is fixed.

A second question concerns the 2-core. Removing pendant trees does not change the cyclomatic number, so one might expect the line-graph signature to be controlled by the 2-core alone. The exact calculation is subtler. Eliminating a pendant tree from $Q(G)-2I$ leaves both an inertia contribution and a diagonal perturbation at its attachment vertex. The perturbation can change the signature, and in some cases it increases it.

The paper develops this observation in four steps.

1.

Section 3 gives an exact attachment formula for pendant trees. It also identifies a scalar response at an attachment vertex and proves that adding one leaf raises the line-graph signature exactly when that response is below $-\tfrac{1}{2}$ .
2.

Section 4 uses the criterion to disprove the monotone 2-core inequality

$s(L(G))\leq\max\{0,s(L(\operatorname{core}_{2}G))\}.$

The first example has ten vertices and cyclomatic number four; a second example shows that the failure already occurs at cyclomatic number two.
3.

Section 5 studies $f(c)=\max\{s(L(G)):c(G)=c\}$ . Explicit constructions give the lower bound $\lfloor(c+1)/2\rfloor$ , and a spanning-tree argument gives the upper bound $c$ .
4.

Section 6 states two open conjectures. The first asks whether extremal 2-cores are stable under pendant attachments. The second bounds the total signature increase produced by a pendant forest. Together they describe what would be needed to prove the conjectured sharp bound $2s(L(G))\leq c(G)+1$ .

The mathematical statements do not depend on the computational searches. Exact computations are used to certify the explicit counterexamples and to test the open conjectures on finite domains. Section 7 separates these finite results from the proofs and states precisely which computations are reproduced by the accompanying package.

2 Definitions and notation

All graphs are finite and simple, and are connected unless stated otherwise. For a graph $G$ , write $A(G)$ for its adjacency matrix, $Q(G)=D(G)+A(G)$ for its signless Laplacian, and

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

The line graph $L(G)$ has vertex set $E(G)$ , with two vertices adjacent when the corresponding edges of $G$ share an endpoint. The 2-core $\operatorname{core}_{2}G$ is the maximal subgraph of minimum degree at least two. For a symmetric real matrix $S$ , write $\operatorname{In}(S)=(n_{+}(S),n_{0}(S),n_{-}(S))$ and $\operatorname{sig}(S)=n_{+}(S)-n_{-}(S)$ . Congruent symmetric matrices have the same inertia, and inertia is additive across an invertible Schur complement [14, 16].

The diagonal entry $(M^{-1})_{xx}$ measures how the inertia changes under a rank-one perturbation at the vertex $x$ . This scalar is the local quantity that controls the effect of attaching a leaf, so we give it a name.

Definition 2.1 (Response at an attachment vertex).

Let $H$ be a graph, let $x\in V(H)$ , and put $M=M(H)$ . If $M$ is invertible, the response at $x$ is

g_{x}=(M^{-1})_{xx}.

If $M$ is singular and $e_{x}\in\operatorname{col}(M)$ , choose any solution of $My=e_{x}$ and define $g_{x}=y_{x}$ . Lemma 3.1 shows that this value is independent of the chosen solution. If $e_{x}\notin\operatorname{col}(M)$ , the response is undefined.

Lemma 2.2 (Vertex-space identity).

For every connected graph $G$ with at least one edge,

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

Proof.

The nonzero spectra of $B^{\top}B=A(L(G))+2I$ and $BB^{\top}=Q(G)$ agree. The remaining zero eigenvalues of $B^{\top}B$ contribute eigenvalues $-2$ to $A(L(G))$ . Counting the eigenvalues on either side of the threshold $2$ in $Q(G)$ gives the stated identity. The bookkeeping, including the bipartite case, is written out in Appendix A. ∎

3 Attachment formulas for pendant trees

This section records the matrix identities needed to remove pendant trees from $M(G)$ . The underlying tools are classical Schur-complement and congruence arguments [14, 4]. The new point for the present problem is their specialization to $Q(G)-2I$ , together with the $-\tfrac{1}{2}$ threshold in Lemma 3.3 and the exact 2-core formula in Proposition 3.6.

Lemma 3.1 (Range-compatible attachment lemma).

Let $K$ be a symmetric $k\times k$ matrix, let $e\in\mathbb{Q}^{k}$ , and suppose that $Ky=e$ is solvable. Let $C$ be symmetric, let $z$ be a 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

\operatorname{In}(S)=\operatorname{In}(K)+\operatorname{In}\!\left(C-(e^{\top}% y)zz^{\top}\right).

Proof.

If $Ky=Ky^{\prime}=e$ , then $y-y^{\prime}\in\ker K$ . Since $K$ is symmetric,

e^{\top}(y-y^{\prime})=(Ky)^{\top}(y-y^{\prime})=y^{\top}K(y-y^{\prime})=0.

Thus $e^{\top}y$ is well defined. With $T=\begin{pmatrix}I&-yz^{\top}\\ 0&I\end{pmatrix}$ , direct block multiplication gives

T^{\top}ST=K\oplus\left(C-(e^{\top}y)zz^{\top}\right).

The matrix $T$ is invertible, so Sylvester’s law of inertia completes the proof. ∎

Remark 3.2.

For invertible $K$ , Lemma 3.1 is the usual Schur-complement formula with $e^{\top}y=e^{\top}K^{-1}e$ . Range-compatible generalized Schur complements for singular blocks are classical [4], and a closely related cut-vertex congruence for adjacency matrices appears in Wang and Fan [26]. The lemma is included to fix the exact form used below and to cover singular attachment vertices without introducing a pseudoinverse.

Lemma 3.3 (Effect of adding one leaf).

Let $H$ be connected, let $x\in V(H)$ , and let $G$ be obtained by adding one leaf adjacent to $x$ . Then

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

If the response $g_{x}$ of Definition 2.1 is defined, then

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

Consequently $s(L(G))-s(L(H))\in\{-1,0,1\}$ , and the change is $+1$ exactly when $g_{x}<-\tfrac{1}{2}$ .

Proof.

Order the new leaf first. Its diagonal entry in $M(G)$ is $-1$ , and the edge to $x$ raises the $x$ -diagonal of $M(H)$ by one. Pivoting on the leaf therefore gives

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

which proves the first formula.

For the rank-one update, consider

S=\begin{pmatrix}-\tfrac{1}{2}&e_{x}^{\top}\\ e_{x}&M(H)\end{pmatrix}.

Pivoting on the upper-left entry gives

\operatorname{In}(S)=(0,0,1)+\operatorname{In}\bigl{(}M(H)+2e_{x}e_{x}^{\top}% \bigr{)}.

Pivoting instead on $M(H)$ , using Lemma 3.1 when $M(H)$ is singular, gives

\operatorname{In}(S)=\operatorname{In}(M(H))+\operatorname{In}(-\tfrac{1}{2}-g% _{x}).

Comparing the two expressions yields the three cases. Finally, $c(G)=c(H)$ , so Lemma 2.2 identifies the change in $\operatorname{sig}M$ with the change in line-graph signature. ∎

Remark 3.4 (Three related changes).

It is useful to keep three quantities separate. The net change after adding the leaf is

\Delta_{M}=\operatorname{sig}M(G)-\operatorname{sig}M(H)\in\{-1,0,1\}.

The rank-one update inside the proof has jump

J=\operatorname{sig}\bigl{(}M(H)+2e_{x}e_{x}^{\top}\bigr{)}-\operatorname{sig}% M(H)\in\{0,1,2\}.

They satisfy $\Delta_{M}=J-1$ . Because the cyclomatic number is unchanged, $\Delta_{M}=s(L(G))-s(L(H))$ .

Lemma 3.5 (Rooted-tree invertibility and parity).

For a rooted tree $(T,r)$ , define

C_{T}=Q(T)-2I+e_{r}e_{r}^{\top}.

Then $C_{T}$ is nonsingular, and the response $\rho=(C_{T}^{-1})_{rr}$ is a rational number whose reduced numerator and denominator are both odd. In particular, the response of every pendant rooted tree is defined.

Proof.

Proceed by induction on $|T|$ . For a single vertex, $C_{T}=(-1)$ and $\rho=-1$ .

Suppose that the root has children carrying rooted subtrees $(T_{i},r_{i})$ with responses $\rho_{i}=p_{i}/q_{i}$ in lowest terms. By induction, $p_{i}$ and $q_{i}$ are odd. Eliminating the child blocks leaves the scalar

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

Modulo two, $Q\equiv 1$ and

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

Thus $N$ is odd and nonzero, so the reduced root block is nonsingular. Its inverse entry is $\rho=1/a=Q/N$ , which again has odd numerator and odd denominator after reduction. ∎

Proposition 3.6 (Exact reduction to the 2-core).

Let $G$ be connected with nonempty 2-core $H=\operatorname{core}_{2}G$ . At a core vertex $x$ , let $(T_{x,j},r_{x,j})$ be the pendant rooted trees. Write

\sigma_{x,j}=\operatorname{sig}C_{T_{x,j}},\qquad\rho_{x,j}=(C_{T_{x,j}}^{-1})% _{r_{x,j}r_{x,j}}.

Set

\tau=\sum_{x,j}\sigma_{x,j},\qquad D_{xx}=\sum_{j}(1-\rho_{x,j}).

Then

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

Proof.

Eliminate the pendant trees one at a time, starting with the branches farthest from the 2-core. The block belonging to a rooted branch is $C_{T}$ , which is nonsingular by Lemma 3.5. Lemma 3.1 replaces that block by its inertia contribution $\operatorname{sig}C_{T}$ and changes the diagonal entry at the attachment vertex by $1-\rho$ . Summing these independent contributions gives the formula. ∎

Figure 1: Eliminating pendant trees does not simply recover the unperturbed 2-core. It produces the diagonally perturbed matrix

M(H)+D

Proposition 3.7 (Recurrence for a rooted tree).

Let the root of $(T,r)$ have $k$ child subtrees with states $(\sigma_{i},\rho_{i})$ . Put

a=(k-1)-\sum_{i}\rho_{i}.

Then

(\sigma,\rho)=\left(\sum_{i}\sigma_{i}+\operatorname{sign}(a),\ \frac{1}{a}% \right).

The one-vertex tree has state $(-1,-1)$ , and Lemma 3.5 ensures that $a\neq 0$ for every rooted tree. Together with Lemma 3.1, the pair $(\sigma,\rho)$ determines the signature effect of attaching the rooted tree at a single attachment vertex whenever the scalar response is defined.

Proof.

Eliminating the child blocks leaves the scalar $a$ at the root. Inertia additivity contributes $\operatorname{sign}(a)$ to the signature, and the root response is $1/a$ . ∎

Remark 3.8.

The recurrence is a complete description of pendant rooted trees, but its state space is infinite. For example, the star with $k$ leaves has state $(1-k,1/(2k-1))$ . Algebraic one-vertex states that do not come from rooted trees may have $a=0$ ; in that case a scalar response is insufficient and one must retain range and nullspace information.

Remark 3.9 (The state does not satisfy simple converses).

Finite exact enumeration shows that the implication $\sigma=0\Rightarrow\rho=1$ holds for rooted trees through order thirteen, but the converse fails: at order ten exactly three rooted trees have state $(-2,1)$ . A second proposed inequality, $1-\rho\leq 2|\sigma|$ , fails at order eleven, where a rooted tree has state $(-3,-21)$ . These observations are finite exact results, not general theorems.

4 Counterexamples to 2-core monotonicity

Proposition 3.6 is an exact reduction, but it involves the perturbed matrix $M(H)+D$ . The diagonal correction cannot in general be removed. The two graphs in Figure 2 show the failure at cyclomatic numbers four and two.

(a) A subdivided edge of $K_{3,3}$ , with a leaf at $x$ .

(b) A $C_{4}$ and a $C_{5}$ joined through $x$ , with a leaf at $x$ .

Figure 2: The 2-core counterexamples. Removing the leaf returns the entire 2-core in each case, but the leaf increases the line-graph signature by one.

Theorem 4.1 (A ten-vertex counterexample with $c=4$ ).

Let $H$ be obtained from $K_{3,3}$ by replacing one edge with a path of length four. Let $x$ be the subdivision vertex adjacent to one endpoint of the replaced edge, and let $G$ be obtained by adding one leaf at $x$ . Then

\operatorname{In}(A(L(H)))=(6,0,6),\qquad\operatorname{In}(A(L(G)))=(7,0,6).

In particular,

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

s(L(G))>\max\{0,s(L(\operatorname{core}_{2}G))\}.

Proof.

The graph $H$ has nine vertices, twelve edges and cyclomatic number four, and it is the 2-core of $G$ . Exact rational elimination gives

g_{x}=-\frac{3}{2}

for $M(H)$ . Lemma 3.3 therefore shows that the added leaf increases the line-graph signature by one. The exact inertias above follow from the characteristic polynomial and root count recorded in Appendix B. The conjectured sharp bound is not contradicted: $2s(L(G))=2\leq c(G)+1=5$ . ∎

Theorem 4.2 (A counterexample with $c=2$ ).

Let $H$ consist of a $4$ -cycle and a $5$ -cycle joined by a path of length two, and let $x$ be the internal vertex of that path. Let $G$ be obtained by adding one leaf at $x$ . Then $M(H)$ is singular, $e_{x}\in\operatorname{col}(M(H))$ , and the response at $x$ is

g_{x}=-\frac{3}{4}.

Moreover,

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

Thus the monotone 2-core inequality already fails at cyclomatic number two. The same example disproves a uniform lower bound $g_{x}\geq-1/2$ on 2-cores and shows that a rank-one diagonal update can increase $\operatorname{sig}M$ by two.

Proof.

The base graph $H$ has ten vertices, eleven edges and cyclomatic number two. Solving $M(H)y=e_{x}$ exactly gives $y_{x}=-3/4$ . Lemma 3.3, in the singular form supplied by Lemma 3.1, gives a signature increase of one. The exact inertias and characteristic polynomial are listed in Appendix B. Again the sharper conjecture survives: $2s(L(G))=2\leq 3=c(G)+1$ . ∎

Remark 4.3 (What is known about minimality).

The graph in Theorem 4.1 is the smallest counterexample found in the searches performed for this work, but global minimality is not proved. The relevant finite results are as follows.

Domain	Method	Result
Connected graphs with at least one edge, orders $2$ – $7$ (995 graphs)	exact, reproduced by the package	no counterexample
Connected graphs of order $8$ (11,117 graphs)	previous exact computation, not rerun by the package	no counterexample
One-leaf attachments to order- $8$ minimum-degree-two cores (59,536 cases)	previous exact computation	no smaller counterexample
Minimum-degree-two graphs with $c\leq 4$ and $n\leq 10$	previous exact computation	no smaller counterexample in that domain
Connected graphs of order $9$	numerical screening only	no candidate found

An exact order-nine census is therefore still required before the nine-vertex case can be excluded.

5 Bounds at fixed cyclomatic number

Definition 5.1.

For $c\geq 0$ , define

f(c)=\max\{s(L(G)):G\text{ is connected and }c(G)=c\},

provided the maximum exists.

The next proposition is a short consequence of published results on tree Laplacian spectra. It is included because it shows that $f(c)$ is finite; no novelty is claimed for the ingredients.

Proposition 5.2 (General upper bound).

For every connected simple graph $G$ ,

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

Consequently $f(c)$ exists and satisfies $f(c)\leq c$ .

Proof.

Let $T$ be a tree on $n\geq 2$ vertices. Since $T$ is bipartite, $Q(T)$ and the Laplacian of $T$ have the same spectrum. Zhou, Zhou and Du [28] show that at least $\lceil n/2\rceil$ Laplacian eigenvalues lie in $[0,2)$ . When $n$ is even and equality occurs, the perfect-matching case of Li, Shiu and Chang [17] supplies an eigenvalue equal to $2$ . In both cases

\operatorname{sig}(Q(T)-2I)\leq-1,

and Lemma 2.2 gives $s(L(T))\leq 0$ . The one-vertex tree is immediate.

Now choose a spanning tree $T$ of $G$ . The edges of $T$ index a principal submatrix $A(L(T))$ of $A(L(G))$ of codimension

|E(G)|-|E(T)|=c(G).

Interlacing yields $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).

Because the signatures are integers and connected graphs exist for every cyclomatic number, the supremum is attained. ∎

Theorem 5.3 (Lower bound for every $c$ ).

For every integer $c\geq 1$ ,

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

Proof.

For odd $c=2k+1$ , the amplifier family $F_{k}$ from [22] satisfies

\operatorname{In}(L(F_{k}))=(6k+3,0,5k+2),\qquad s(L(F_{k}))=k+1=\frac{c+1}{2}.

For even $c=2j$ , start with $F_{j-1}$ and attach a $4$ -cycle by one bridge, as shown in Figure 3. In the edge ordering $(b,wx,xy,yz,zw)$ , the line-graph block of the five new edges has inertia $(2,1,2)$ . The vector

y=(0,1,0,-1,0)^{\top}

satisfies $Ky=e_{b}$ and $e_{b}^{\top}y=0$ . Lemma 3.1 therefore shows that the attachment adds one cycle without changing the signature. Thus

s(L(G))=j=\left\lfloor\frac{2j+1}{2}\right\rfloor.

∎

Figure 3: The singular

C_{4}

attachment used for even cyclomatic number. It increases

c(G)

by one and leaves the line-graph signature unchanged.

Combining Proposition 5.2 and Theorem 5.3 gives

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

Two explicit construction families attain the lower value through $c=13$ . They are isomorphic for $c\leq 3$ and non-isomorphic for $4\leq c\leq 13$ ; this finite comparison is not used in the proof.

Conjecture 5.4 (Sharp bound at fixed cyclomatic number).

For every connected simple graph $G$ ,

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

Equivalently,

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

No counterexample is known. The conjecture has been checked exactly on all connected graphs of order at most eight, although the accompanying package reproduces only the part through order seven. A complete traversal at order nine found no candidate numerically, but that computation is not an exact verification. Further finite tests are summarized in Section 7.

6 Pendant attachments on extremal cores

A minimum-degree-two graph $H$ with cyclomatic number $c$ will be called extremal when

s(L(H))=\left\lfloor\frac{c+1}{2}\right\rfloor.

The counterexamples in Section 4 arise from attachment vertices with response below $-1/2$ . In the finite computations, no such vertex was found on an extremal core. This motivates the following conjecture.

Conjecture 6.1 (Stability of extremal cores).

Let $H$ be an extremal minimum-degree-two graph. Then no vertex $x$ of $H$ has response $g_{x}<-\tfrac{1}{2}$ . Equivalently, adding one leaf to $H$ never increases $s(L(H))$ .

More strongly, attaching any pendant forest to an extremal core does not increase the line-graph signature.

The one-leaf statement does not automatically imply the pendant-forest statement, because diagonal changes at different vertices interact in Proposition 3.6. Both assertions are therefore open. Moreover, stability of extremal cores alone does not prove Conjecture 5.4: a non-extremal core may gain signature while still remaining below the conjectured maximum. The required quantitative statement is the following.

Conjecture 6.2 (Bound on the increase from pendant forests).

Let $G$ be connected with nonempty 2-core $H$ . Then

s(L(G))-s(L(H))\leq\left\lfloor\frac{c(G)+1-2s(L(H))}{2}\right\rfloor.

Since $c(G)=c(H)$ , this inequality says that pendant trees cannot increase the signature by more than the difference between the core’s signature and the conjectured extremal value. If the 2-core satisfies Conjecture 5.4, then Conjecture 6.2 implies the same bound for $G$ . Its extremal case is the strong part of Conjecture 6.1.

The exact tests described in Section 7 found no violation of either conjecture. They also found many positive leaf gains on non-extremal cores, which confirms why an argument based only on extremal stability would be incomplete.

7 Computational verification

The computations serve two purposes: they certify the explicit examples and test the open conjectures on finite domains. They are not used as substitutes for the proofs in Sections 3 and 5.

All results labelled exact were obtained without floating-point arithmetic. The main methods were rational symmetric congruence and integer characteristic polynomials with certified real-root counts. The two central counterexamples were also recomputed in a separate computer-algebra system.

Object or domain	Exact scope and method	Reproduction status
Counterexamples in Theorems 4.1 and 4.2	rational congruence, exact characteristic polynomials, certified root counts	fully reproduced
Leaf criterion	2,537 nonsingular vertex cases, including the boundary $g_{x}=-1/2$ ; 300 singular solvable-vertex cases	fully reproduced
Rooted-tree recurrence and parity	all 141,083 rooted trees of order at most 15	fully reproduced
Pendant-tree reduction	all 1,205 rooted trees of order at most 10 and the two central counterexamples	fully reproduced
Connected graphs, orders $2$ – $7$	995 connected graphs with at least one edge	fully reproduced
Connected graphs, order $8$	11,117 graphs; together with lower orders, 12,113 through order $8$	previous exact computation; not rerun by the package
Connected graphs, order $9$	complete numerical traversal	screening only
Structured exact searches	minimum-degree-two graphs with $c\leq 4$ , $n\leq 10$ ; 59,536 one-leaf updates; 12,474 rooted chorded-cycle cases; 1,305 three-cycle chains	previous exact computations; not rerun by the package
Response boundary cases	2,563 exact cases with $g_{x}=-1/2$ ; minimum observed response $-29/6$ on a non-extremal core	previous exact computations; not rerun by the package
Extremal-core attachment tests	720 isomorphism classes of base graphs; 14 extremal classes; 1,400 two-leaf support pairs on 11 extremal classes	exact within the stated domain
Explicit extremal families	both families through $c=13$	fully reproduced
Endpoints $c=14,\ldots,20$	one construction family	previous exact computation; not rerun by the package

In the extremal-core tests, no extremal graph had a response below $-1/2$ , and neither one-leaf nor two-leaf attachments increased its signature. On non-extremal graphs, 416 one-leaf increases were observed; every one remained within the bound proposed in Conjecture 6.2. These are bounded negative tests and do not prove either conjecture.

Graph generation was cross-checked against standard counts. Connected graphs through order seven were taken from the Graph Atlas, and rooted trees were generated independently using the Beyer–Hedetniemi method [3]. The accompanying reproducibility package contains the scripts, exact certificates, graph encodings, expected outputs, environment information, manifest and checksums. Appendix C states which parts of the table are and are not reproduced by that package.

8 Relationship to previous work

8.1 The source conjecture and its refutations

Conjecture (1) and its partial results are due to Akbari, Elphick, Kumar, Pragada and Tang [1]. Paone’s first preprint gives an exact connected counterexample [21]; a second preprint develops unbounded families and transfer principles [22]. Francis and Uptain independently obtain exact connected counterexamples and an unbounded chaining construction [11]. The unboundedness preprints of Paone and of Francis–Uptain carry the same public date; no intraday priority claim is made. Their work is directly relevant to refutation and unboundedness. The present paper addresses different questions: the effect of pendant trees, the failure of 2-core monotonicity, and extremal signature at fixed cyclomatic number. Chen and Li [5] concern the global quadratic inertia conjecture rather than the line-graph conjecture.

8.2 Cycle structure and the threshold $2$

Ma, Yang and Li [19] proposed signature bounds in terms of cycle counts modulo four and proved them for several graph classes. Wang and Fan [26] proved the corresponding bounds for line graphs. Those results use cycle counts in the line graph, whereas Conjecture 5.4 uses the cyclomatic number of the root graph.

Several papers study the multiplicity of the signless-Laplacian eigenvalue $2$ or the number of eigenvalues on one side of that threshold. Zhao and Yu [27], Li, Guo, Tian and Wang [18], and Batal [2] give circuit-rank bounds on relevant multiplicities. Wang and Belardo [25] and Feng, Wang and Belardo [10] classify graphs with few signless-Laplacian eigenvalues above or at $2$ . These results constrain the nullity or one side of the inertia of $Q(G)-2I$ . The line-graph signature, however, depends on the difference between the numbers of eigenvalues above and below $2$ . Accordingly, none of these results directly yields the conjectured inequality $2s(L(G))\leq c(G)+1$ .

8.3 Trees and the general upper bound

The inertia of line graphs of trees has been studied directly [13, 20]. For the argument in Proposition 5.2, the relevant inputs are the count of tree Laplacian eigenvalues below $2$ due to Zhou, Zhou and Du [28] and the perfect-matching equality case of Li, Shiu and Chang [17]. The passage from a spanning tree to the bound $s(L(G))\leq c(G)$ is then an immediate interlacing argument. We do not claim that coarse upper bound as an independent new theorem.

8.4 Attachments, inverse diagonals and singular blocks

Schwenk’s coalescence formulas [23] and the rooted-product formulas of Godsil and McKay [12] are classical spectral tools for attaching rooted graphs. Haynsworth inertia additivity [14] and range-compatible singular Schur complements [4] supply the matrix mechanism used here. Wang and Fan [26] use a related solvable-column congruence for adjacency matrices.

For an invertible symmetric matrix $K$ , the identity $(K^{-1})_{xx}=\det K[x]/\det K$ relates an inverse diagonal to a vertex-deleted principal minor. Vanishing inverse diagonals are central in the NSSD literature [8, 9]. The response used here is the same scalar for the shifted signless Laplacian $Q-2I$ , but the relevant condition is the inequality $g_{x}<-1/2$ , not vanishing. Lemma 3.1 extends the calculation to singular matrices when the coordinate vector lies in the column space.

8.5 Classical line-graph structure and subdivision

The spectral theory of graphs with least eigenvalue at least $-2$ is classical [6]; related signature results appear in [15]. Four-subdivision invariance for inertia is available in [19], and an integral line-graph refinement appears in [22]. General inertia bounds involving matching and cyclomatic number for adjacency matrices, rather than line graphs, are given in [7]. Standard Smith-normal-form background is in [24].

The literature reviewed for this manuscript did not reveal a published result stating or directly implying the sharper bound $2s(L(G))\leq c(G)+1$ , the leaf threshold of Lemma 3.3, or the exact pendant-tree reduction of Proposition 3.6. This is a limited literature statement, not an absolute priority claim. No novelty is claimed for Schur complements, rooted products, coalescence formulas, interlacing, or the coarse upper bound $s(L(G))\leq c(G)$ .

9 Limitations and open problems

1.

Exact order-nine census. The order-nine search used numerical screening. An exact census would test Conjecture 5.4 and would also determine whether the ten-vertex graph in Theorem 4.1 is globally minimal.
2.

Sharp upper bound. Proposition 5.2 gives $f(c)\leq c$ . The main open problem is to prove or refute $2s(L(G))\leq c(G)+1$ .
3.

Stability of extremal cores. Prove or refute Conjecture 6.1. Large even-cyclomatic examples are among the first untested families.
4.

Total effect of a pendant forest. Prove or refute Conjecture 6.2. This quantitative statement, rather than single-leaf stability alone, is what a proof by reduction to the 2-core would need.
5.

Several attachment vertices. Develop a response-matrix version of Lemma 3.1 that retains the necessary range and nullspace information for singular blocks with several attachment vertices.
6.

Kernel enumeration. After suppressing degree-two paths, a minimum-degree-three kernel with cyclomatic number $c$ has at most $2c-2$ vertices. Exact enumeration gives $3$ , $15$ and $111$ kernels for $c=2,3,4$ . Extending the enumeration to $c=5$ would make a kernel-based approach concrete for the next case.
7.

Equality cases. Classify the graphs attaining $\lfloor(c+1)/2\rfloor$ , allowing for four-subdivision and attachments that leave the signature unchanged. The classification of three-cycle chains in [22] provides a starting point.
8.

Algorithms at fixed $c$ . Kernel reduction and exact response data suggest a fixed-parameter approach. The rooted-tree state space is infinite, so a finite algorithm would need an equivalence relation that preserves only the inequalities relevant to the signature. The resulting bit complexity is open.

Conclusion

Pendant trees influence the line-graph signature through explicit diagonal corrections on the 2-core. The response at an attachment vertex determines the effect of one leaf, and responses below $-1/2$ produce exact counterexamples to monotone 2-core reduction. The failure already occurs at cyclomatic number two.

At fixed cyclomatic number, the signature is nevertheless bounded:

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

The lower bound is attained by explicit constructions, and the upper bound follows from tree spectra and interlacing. Determining the exact value of $f(c)$ , and understanding how pendant forests behave on extremal cores, remain the principal open problems.

Appendix A Additional proof details

A.1 Spectral bookkeeping for Lemma 2.2

Let $B$ be the $n\times m$ unoriented incidence matrix. The matrices $B^{\top}B=A(L(G))+2I$ and $BB^{\top}=Q(G)$ have the same nonzero eigenvalues. Let $z_{Q}$ be the nullity of $Q(G)$ , and let $q_{+}$ , $q_{2}$ and $q_{-}$ count the positive eigenvalues of $Q(G)-2I$ , its zero eigenvalues, and the eigenvalues of $Q(G)$ in $(0,2)$ , respectively. Since $\operatorname{rank}B=n-z_{Q}$ , the extra zero eigenvalues of $B^{\top}B$ have multiplicity $m-n+z_{Q}$ . Therefore

n_{+}(L(G))=q_{+},\qquad n_{-}(L(G))=q_{-}+m-n+z_{Q},

whereas

\operatorname{sig}(Q(G)-2I)=q_{+}-q_{-}-z_{Q}.

Subtracting gives

s(L(G))=\operatorname{sig}(Q(G)-2I)-(m-n)=\operatorname{sig}(M(G))-c(G)+1.

The separation of the zero eigenvalues of $Q(G)$ is necessary in the bipartite case.

A.2 The undefined-response case in Lemma 3.3

If $e_{x}\notin\operatorname{col}(M(H))$ , the scalar response is undefined. A direct congruence of the bordered matrix used in the proof produces a hyperbolic pair, and the rank-one update changes the signature by one. None of the counterexamples or constructions in this paper uses this case.

A.3 Relation between Conjectures 6.1 and 6.2

If the 2-core $H$ is extremal, the strong form of Conjecture 6.1 says that a pendant forest produces no positive net change. If $H$ is not extremal, that statement gives no bound on the amount of a possible increase. Conjecture 6.2 supplies the missing quantitative estimate. Because $c(G)=c(H)$ ,

s(L(G))\leq s(L(H))+\left\lfloor\frac{c(G)+1-2s(L(H))}{2}\right\rfloor\leq% \left\lfloor\frac{c(G)+1}{2}\right\rfloor

whenever the 2-core satisfies the conjectured sharp bound.

A.4 The even- $c$ attachment in Theorem 5.3

Let $b=vw$ be the bridge from the base graph to a $4$ -cycle $w x y z$ . In the edge ordering $(b,wx,xy,yz,zw)$ , the line-graph block of the new edges is

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},\qquad\operatorname{In}(K)=(2,1,2).

For $y=(0,1,0,-1,0)^{\top}$ , one has $Ky=e_{b}$ and $e_{b}^{\top}y=0$ . The coupling to the line graph of the base graph has the form $e_{b}z^{\top}$ . Lemma 3.1 therefore adds the inertia $(2,1,2)$ and leaves the signature unchanged.

Appendix B Exact certificates for the principal examples

The graph encodings below use graph6. They are included so that the examples can be reconstructed independently of the figures.

The ten-vertex example of Theorem 4.1

base graph $H$	HBzc?CP (isomorphic encoding: HsX_WCP)
graph $G$	IBzc?CP?_ (isomorphic encoding: IsX_WCP?O)
parameters	$n(G)=10$ , $m(G)=13$ , $c(G)=4$
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}=-3/2$

The characteristic polynomial of $A(L(G))$ is

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

The cyclomatic-number-two example of Theorem 4.2

base graph $H$	Il?GGCHa?
graph $G$	Jl?GGCHa??_
parameters	$n(G)=11$ , $c(G)=2$
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	$M(H)$ singular, range response $g_{x}=-3/4$

The characteristic polynomial of $A(L(G))$ is

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{)}.

Earlier seed example

The bridge chain $C_{5}$ – $C_{4}$ – $C_{5}$ has $n=14$ , $m=16$ , $c=3$ and

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

This is the counterexample first reported in [21] and used in the later construction paper [22].

Rooted-tree state examples

The first finite counterexamples to the converse $\rho=1\Rightarrow\sigma=0$ occur at order ten, where exactly three rooted trees have state $(-2,1)$ . An order-eleven rooted tree has state $(-3,-21)$ , disproving the proposed inequality $1-\rho\leq 2|\sigma|$ . Encodings and direct matrix calculations are included in the supplementary data.

Appendix C Computational details and package scope

The exact inertia calculations use symmetric elimination over $\mathbb{Q}$ . For the principal examples, an independent route forms the integer characteristic polynomial and counts real roots exactly on the intervals $(-\infty,0)$ , $\{0\}$ and $(0,\infty)$ . The graph6 strings in Appendix B allow the matrices to be reconstructed directly.

The accompanying package reproduces:

•

the two counterexamples and their responses;
•

the connected-graph census through order seven;
•

the rooted-tree recurrence and parity test through order fifteen;
•

the pendant-tree reduction tests through order ten;
•

the stated extremal constructions through $c=13$ ;
•

the finite extremal-core attachment tests described in Section 7.

The package does not reproduce the exact order-eight census, the exact endpoints $c=14,\ldots,20$ , or several larger structured searches. Those results are retained in the manuscript only with that limitation stated. The order-nine traversal uses floating-point eigenvalues and is reported only as screening. No finite computation is used as a proof of a universal statement.

Author contributions

Andrea Paone and Marco Paone contributed equally to this work.

Funding

The authors received no external funding for this work.

Disclosure statement

No potential conflict of interest was reported by the authors.

Use of generative AI and AI-assisted tools

During the research and preparation of this manuscript, the authors used OpenAI GPT-5.6 (High and Pro configurations), Anthropic Claude Opus 5 and Claude Fable 5, and AI-assisted coding tools to assist with exploratory calculations, code development and checking, literature triage, and language and LaTeX editing. The authors checked all mathematical statements, proofs, citations, exact certificates and computational results and take full responsibility for the integrity and accuracy of the manuscript. AI systems were not treated as authors or as sources of mathematical authority.

Data availability statement

The verification code, exact certificates, graph encodings, data tables and expected outputs supporting the mathematical results are available at doi:10.5281/zenodo.21706797. The complete version history is available under the concept DOI doi:10.5281/zenodo.21570993. First-party material is licensed under CC BY 4.0; third-party dependencies 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: §1, §8.1.
[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: §8.2.
[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: §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, §8.4.
[5] H. Chen and J. Li (2026) Counterexamples to a conjecture on graph inertia. Note: arXiv:2605.07196, preprint Cited by: §1, §8.1.
[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: §8.5.
[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: §8.5.
[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: §8.4.
[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: §8.4.
[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: §8.2.
[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: §1, §8.1.
[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: §8.4.
[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: §8.3.
[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, §8.4.
[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: §8.5.
[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: §5, §8.3.
[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: §8.2.
[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: §8.2, §8.5.
[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: §8.3.
[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, §1, §8.1.
[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, §1, §5, §8.1, §8.5, item 7.
[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: §8.4.
[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: §8.5.
[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: §8.2.
[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: Remark 3.2, §8.2, §8.4.
[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: §8.2.
[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: §5, §8.3.

Line-Graph Signature Beyond the 2-Core: Counterexamples, Pendant Attachments, and Bounds at Fixed Cyclomatic Number

Abstract

1 Introduction

2 Definitions and notation

Definition 2.1 (Response at an attachment vertex).

Lemma 2.2 (Vertex-space identity).

Proof.

3 Attachment formulas for pendant trees

Lemma 3.1 (Range-compatible attachment lemma).

Proof.

Remark 3.2.

Lemma 3.3 (Effect of adding one leaf).

Proof.

Remark 3.4 (Three related changes).

Lemma 3.5 (Rooted-tree invertibility and parity).

Proof.

Proposition 3.6 (Exact reduction to the 2-core).

Proof.

Proposition 3.7 (Recurrence for a rooted tree).

Proof.

Remark 3.8.

Remark 3.9 (The state does not satisfy simple converses).

4 Counterexamples to 2-core monotonicity

Theorem 4.1 (A ten-vertex counterexample with c=4).

Proof.

Theorem 4.2 (A counterexample with c=2).

Proof.

Remark 4.3 (What is known about minimality).

5 Bounds at fixed cyclomatic number

Definition 5.1.

Proposition 5.2 (General upper bound).

Proof.

Theorem 5.3 (Lower bound for every c).

Proof.

Conjecture 5.4 (Sharp bound at fixed cyclomatic number).

6 Pendant attachments on extremal cores

Conjecture 6.1 (Stability of extremal cores).

Conjecture 6.2 (Bound on the increase from pendant forests).

7 Computational verification

8 Relationship to previous work

8.1 The source conjecture and its refutations

8.2 Cycle structure and the threshold 2

8.3 Trees and the general upper bound

8.4 Attachments, inverse diagonals and singular blocks

8.5 Classical line-graph structure and subdivision

9 Limitations and open problems

Conclusion

Appendix A Additional proof details

A.1 Spectral bookkeeping for Lemma 2.2

A.2 The undefined-response case in Lemma 3.3

A.3 Relation between Conjectures 6.1 and 6.2

A.4 The even-c attachment in Theorem 5.3

Appendix B Exact certificates for the principal examples

The ten-vertex example of Theorem 4.1

The cyclomatic-number-two example of Theorem 4.2

Earlier seed example

Rooted-tree state examples

Appendix C Computational details and package scope

Author contributions

Funding

Disclosure statement

Use of generative AI and AI-assisted tools

Data availability statement

Licence

References

Line-Graph Signature Beyond the 2-Core:
Counterexamples, Pendant Attachments, and Bounds
at Fixed Cyclomatic Number

Theorem 4.1 (A ten-vertex counterexample with $c=4$ ).

Theorem 4.2 (A counterexample with $c=2$ ).

Theorem 5.3 (Lower bound for every $c$ ).

8.2 Cycle structure and the threshold $2$

A.4 The even- $c$ attachment in Theorem 5.3