Pith. sign in

REVIEW 2 major objections 5 minor 13 references

Inertia indices of signed graphs with given cyclomatic number and given number of pendant vertices

T0 review · 2 major / 5 minor · reviewed 2026-08-06 · deepseek-v4-flash

Pith's one-line read The paper proves a sharp lower bound for the positive inertia index of signed graphs in terms of cyclomatic number and pendant vertices, and classifies equality as disjoint unions of signed cycles with lengths 0 mod 4 (balanced) or 2 mod…

desk verdict A genuine signed-graph extension of the Ma–Wong–Tian bound, but the proof of the stronger bound contains an off-by-one error in the unique-pendant case that must be fixed. read the letter →

arxiv 2506.23112 v1 pith:NJKB573P submitted 2025-06-29 math.SP math.STstat.TH

classification math.SPmath.STstat.TH MSC 05C5005C22
keywords inertiaindicespositiveindexnegativenullitycyclomaticnumberpendantverticessignedgraphsextremal
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

This paper proves a sharp lower bound on the number of positive eigenvalues (the positive inertia index) of a signed graph in terms of two crude structural numbers: how many independent cycles it has and how many pendant leaves it has. For a connected signed graph of order $n$, the bound reads $i_+(\Gamma) \ge (n-p(\Gamma))/2 - \theta(\Gamma)$, and it improves to $(n-p(\Gamma)+1)/2 - \theta(\Gamma)$ whenever there is at least one leaf or two distinct cycles meet. The paper then characterizes every signed graph that reaches the original bound: a disjoint union of signed cycles whose lengths are $0 \bmod 4$ when balanced and $2 \bmod 4$ when unbalanced. The same inequalities for the negative inertia index and for the nullity follow immediately by symmetry, recovering and extending known bounds for ordinary graphs.

What carries the argument

The proof runs by induction on the number of vertices. Two elementary tools carry the load: interlacing, which gives $i_+(\Gamma) \ge i_+(\Gamma-x)$ for induced subgraphs, and a pendant-vertex deletion rule, which says that deleting a leaf together with its neighbor reduces both inertia indices by exactly one. A counting lemma (Lemma 2.4) tracks how the cyclomatic number changes under deleting a vertex $x$, giving $\theta(\Gamma-x)=\theta(\Gamma)-d(x)+s$, and bounds the degree $d(x)$ against the number of components $s$ of $\Gamma-x$. For the equality classification, the paper contracts each induced signed cycle to a vertex, producing a tree, and uses the explicit inertia formulas for signed paths and cycles to force each component to be a single cycle of the stated congruence class.

What would settle it

Enumerate all connected signed graphs of order at most 8 with $p(\Gamma)=0$ and $\theta(\Gamma)=2$ and compute $i_+(\Gamma)$ directly: any such graph with $i_+(\Gamma)=n/2-\theta(\Gamma)$ whose cycles share a vertex would contradict the necessity direction of Theorem 3.2. Alternatively, check the unproved degree-counting step by looking for a vertex lying on two distinct cycles with $d(x)<s+2$.

Watch

Extended reading notes

Core claim

The central claim is that the positive inertia index of a signed graph is controlled from below by the combinatorial surplus of non-leaf vertices over independent cycles. Written as $i_+(\Gamma) \ge (n-p(\Gamma))/2 - \theta(\Gamma)$, this is Theorem 3.1; the 'moreover' clause sharpens the numerator by one when $p(\Gamma) \ge 1$ or when $p(\Gamma)=0$ and two distinct cycles share vertices. Theorem 3.2 settles the extremal case: equality holds exactly for disjoint unions of signed cycles $C_{n_i}$ with $n_i \equiv 0 \pmod 4$ when the cycle is balanced and $n_i \equiv 2 \pmod 4$ when it is unbalanced, with all components of order at least two. The paper derives the analogous inequality for $i_-(\Gamma)$ by negating the signature, and combines the two to get $\eta(\Gamma) \le p(\Gamma)+2\theta(\Gamma)$, with a one-unit improvement under the same extra hypotheses.

Load-bearing premise

The argument's load-bearing premise is an unstated graph fact: when a vertex lies on two distinct cycles and has degree at least three in their union, deleting it leaves at least two fewer components than its degree; the proof asserts this with 'which implies' rather than proving it, and both the stronger bound and the equality classification rely on it.

Editorial extensions

If this is right

  • The inequality for $i_+(\Gamma)$ immediately gives the same lower bound for $i_-(\Gamma)$, since negating all signs swaps the two inertia indices.
  • Adding the two bounds yields the nullity ceiling $\eta(\Gamma) \le p(\Gamma)+2\theta(\Gamma)$, and the sharper version $\eta(\Gamma) \le p(\Gamma)+2\theta(\Gamma)-1$ when leaves or intersecting cycles are present.
  • Equality in the positive lower bound can only occur in a disjoint union of signed cycles whose lengths are $0 \bmod 4$ (balanced) or $2 \bmod 4$ (unbalanced); any two cycles sharing a vertex pushes the bound upward.
  • Because $p(\Gamma)$ and $\theta(\Gamma)$ are additive over components, all these statements extend from connected to disconnected signed graphs.
  • For ordinary unsigned graphs, the nullity consequence recovers the known bound that motivated the paper.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The paper characterizes equality only for the weaker bound; the extremal graphs for the strengthened inequality, when leaves exist or when two cycles meet, are not classified, and a family of cycles with attached trees seems the natural candidate.
  • The same induction could yield a rank bound $r(\Gamma) \ge n - p(\Gamma) - 2\theta(\Gamma)$, with equality cases inherited from the two inertia classifications.
  • The unproved degree-counting fact behind the 'moreover' clause, that $d(x) \ge s+2$ for a vertex on two distinct cycles, could be formalized as a lemma and may hold for any vertex whose removal raises the number of components by at least two.
  • A computational check on all connected signed graphs of small order with $p(\Gamma)=0$ and $\theta(\Gamma)=2$ would independently verify the equality classification and could seed a conjecture for the sharpened bound.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 5 minor

Summary. The paper studies the positive and negative inertia indices of signed graphs in terms of the order n, the cyclomatic number θ, and the number of pendant vertices p. The main result (Theorem 3.1) is the inequality i_+(Γ) ≥ (n−p(Γ))/2 − θ(Γ) for connected signed graphs of order n≥2, together with a stronger bound (n−p(Γ)+1)/2 − θ(Γ) when p(Γ)≥1 or when p(Γ)=0 and two distinct cycles share vertices. Theorem 3.2 characterizes the extremal graphs attaining equality as disjoint unions of signed cycles C_{n_i} with n_i≡0 mod 4 if balanced and n_i≡2 mod 4 if unbalanced. By applying the results to the negation of Γ, the paper obtains the analogous statements for i_−, and then derives the nullity bound η(Γ)≤p(Γ)+2θ(Γ), with the improved bound when the stronger hypotheses hold. The proof is by induction on the order, using interlacing, a pendant-vertex reduction lemma (Lemma 2.2), and elementary identities for the cyclomatic number (Lemma 2.4).

Significance. If the proof gaps identified below are repaired, the results are a solid and useful contribution to the spectral theory of signed graphs. The paper gives a clean, parameter-free inequality relating three natural graph invariants, completely characterizes the extremal graphs, and recovers known simple-graph nullity results from [9] as a by-product. The proof is largely elementary and self-contained, and it is not circular: the only self-citation ([4]) is background material and is not used in the proofs. The equality characterization in Theorem 3.2, if fully justified, is a genuine structural result rather than a merely numerical one. The main weaknesses are localized proof gaps: an off-by-one error in the application of Lemma 2.4(ii) in the unique-pendant case, and an unproved graph-theoretic assertion in the intersecting-cycles case.

major comments (2)
  1. [Theorem 3.1, Case 3 (d(y)≥3 subcase)] There is an off-by-one error in the application of Lemma 2.4(ii). The proof defines s as the number of components of (Γ−y)−x. Since x is the pendant neighbor of y, Γ−y consists of these s components together with the isolated vertex x, so Γ−y has s+1 components. Lemma 2.4(ii) therefore gives θ(Γ−y)=θ(Γ)−d(y)+s+1, and deleting the isolated vertex x does not change θ, so θ((Γ−y)−x)=θ(Γ)−d(y)+s+1, not θ(Γ)−d(y)+s as printed. The displayed derivation of i_+(Γ)≥(n+1)/2−θ(Γ) in this subcase is consequently invalid. The gap is repairable: applying Lemma 2.4(i) to Γ at y, with Γ−y having s+1 components, gives d(y)≥m+(s+1)−r; combined with the trivial bound d(y)≥s+1 (every component of (Γ−y)−x contains at least one neighbor of y), one obtains 2d(y)≥2s+m−r+2, which together with the corrected θ yields exactly i_+(Γ)≥n/2−θ(Γ), i.e. the desired stronger bound since p(Γ)=1. The same off-by-one occurs in Theorem 4.1, Case 3, and must be fixed there as well.
  2. [Theorem 3.1, Case 1 (final paragraph)] The assertion that choosing x in the intersection of two distinct cycles with d_{C1∪C2}(x)≥3 implies d(x)≥s+2 is not proved in the text. The statement is true: writing a_k for the number of neighbors of x in the k-th component of Γ−x, the existence of two distinct cycles whose union has degree at least 3 at x forces Σ_k(a_k−1)≥2, hence d(x)=Σ_k a_k≥s+2. However, this fact is load-bearing: it is used to prove the 'moreover' bound in the case p(Γ)=0 with two intersecting cycles, and that bound is in turn used in the equality characterization (Theorem 3.2) and in Corollaries 4.1–4.2. The proof should supply the short argument instead of leaving it to the reader. The analogous step in Theorem 4.1, Case 1, needs the same clarification.
minor comments (5)
  1. [Throughout] There are several typos and grammatical slips: 'Denoted by' should be 'Denote by', 'spire us' should be 'inspire us', 'inequaliy' should be 'inequality', and 'well-know' should be 'well-known'.
  2. [Lemma 2.2] The wording 'deleting u together with the vertices adjacent to it' is ambiguous; the lemma is used for deleting a pendant vertex and its unique neighbor, so it should say 'deleting u and its unique neighbor'.
  3. [Theorem 3.1, Case 3] The sentence 'y must belong to some cycle of Γ because d(y)≥3 and x is unique pendant vertex' is false: for example, take two cycles, connect each by a path to y, and attach the pendant vertex x to y. Then d(y)=3, x is the unique pendant vertex, and y lies on no cycle. The needed bound d(y)≥s+1 holds for the trivial reason that every component of (Γ−y)−x contains at least one neighbor of y, so the incorrect justification should be replaced.
  4. [Theorem 3.2, converse] The claim that contracting each induced signed cycle yields a tree is asserted with 'Clearly' but is part of the structural argument. A sentence explaining that a cycle in the contracted graph would lift to a cycle of Γ sharing vertices with at least two original cycles would make the proof self-contained.
  5. [Lemma 2.5] The domain for signed cycles (n≥3) should be stated explicitly, since the formulas for C_2 are not defined in the simple-graph setting.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity: the main inequality is derived by a self-contained induction from standard lemmas; the only self-citation ([4]) is background, and the two flagged proof defects (Case 3 off-by-one, Case 1 unproved d(x)≥s+2) are correctness gaps, not circular reductions.

full rationale

The derivation chain is not circular. Theorem 3.1 is proved by induction on order n using Lemma 2.2 (pendant deletion, i±(Γ)=i±(Γ′)+1), Lemma 2.4 (proved in full here for signed graphs), and Lemma 2.5 (signed cycle/path inertia, cited from [12,13,14]); none of these inputs contains the target inequality, and the stronger bound for components with pendant vertices is carried through a standard strong induction rather than assumed at the top level. Theorem 3.2 is a genuine deduction: it applies the already-proved Theorem 3.1 to H_i−y and computes cycle inertias from Lemma 2.5, so the equality characterization is not a restatement of the hypotheses. The only self-citation, Duan–Yang [4], appears in the introductory sentence "Recently, there have been a number of investigations on the spectra of signed graphs, see [4, 7, 11]" and does no work in any proof. Two non-circular proof gaps should be weighed by the correctness review. (1) Theorem 3.1, Case 3 (d(y)≥3), final paragraph: the printed equality "θ((Γ−y)−x) = θ(Γ−y) = θ(Γ) − d(y) + s" is off by one — Γ−y has s+1 components (the H_k plus the isolated pendant x), so Lemma 2.4(ii) gives θ(Γ−y)=θ(Γ)−d(y)+s+1; corrected, the displayed algebra yields only the base bound (n−1)/2−θ(Γ), so the 'moreover' strengthening in this subcase, on which Theorems 3.2/4.2 and Corollaries 4.1/4.2 lean, does not follow as written. (2) Theorem 3.1, Case 1, 'Furthermore' paragraph: "d_{C1∪C2}(x) ≥ 3, which implies d(x) ≥ s+2" is stated without proof; the fact is true but unstated. Neither gap makes any result equivalent to its own input, so per the rubric the circularity score is 1, not higher.

Assumptions & free parameters 0 free parameters · 3 assumptions · 0 invented entities

No free parameters are fitted. The proof relies on standard interlacing and on published inertia formulas for signed cycles and paths.

assumptions (3)
  • standard math Interlacing Theorem (Theorem 2.1, cited from Cvetković et al.)
    Used to prove Lemma 2.1 that induced subgraphs have no larger positive inertia index.
  • domain assumption Pendant vertex deletion formula (Lemma 2.2, cited from [13])
    i_+(Γ)=i_+(Γ')+1 when deleting a pendant vertex and its neighbor; used throughout the induction.
  • domain assumption Inertia of signed cycles and paths (Lemma 2.5, cited from [12,13,14])
    Provides the explicit i_+ values for balanced/unbalanced cycles, which are load-bearing for the equality characterization and the base cases.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Inertia indices of signed graphs with given cyclomatic number and given number of pendant vertices." pith.science (2026). https://pith.science/paper/NJKB573P

@misc{pith2026250623112,
  author       = {Pith},
  title        = {Pith review of: Inertia indices of signed graphs with given cyclomatic number and given number of pendant vertices},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/NJKB573P}},
  note         = {Machine review of arXiv:2506.23112}
}
abstract

Let $\Gamma=(G, \sigma)$ be a signed graph of order $n$ with underlying graph $G$ and a sign function $\sigma: E(G)\rightarrow \{+, -\}$. Denoted by $i_+(\Gamma)$, $\theta(\Gamma)$ and $p(\Gamma)$ the positive inertia index, the cyclomatic number and the number of pendant vertices of $\Gamma$, respectively. In this article, we prove that $i_+(\Gamma)$, $\theta(\Gamma)$ and $p(\Gamma)$ are related by the inequality $i_+(\Gamma)\geq \frac{n-p(\Gamma)}{2}-\theta(\Gamma)$. Furthermore, we completely characterize the signed graph $\Gamma$ for which $i_+(\Gamma)=\frac{n-p(\Gamma)}{2}-\theta(\Gamma)$. As a by-product, the inequalities $i_-(\Gamma)\geq \frac{n-p(\Gamma)}{2}-\theta(\Gamma)$ and $\eta(\Gamma)\leq p(\Gamma)+2\theta(\Gamma)$ are also obtained, respectively.

Figures

Figures reproduced from arXiv: 2506.23112 by the authors.

Figure 1
Figure 1. The tree TΓ corresponding to cycle-disjoint signed graph Γ. Proof. Suppose that Γ  C σ n1 ∪C σ n2 ∪· · ·∪C σ nt , where n1+n2+· · ·+nt = n and ni ≡ 0( mod 4) if C σ ni is balanced or ni ≡ 2(mod 4) if C σ ni is unbalanced. Then i+(Γ) = ( n1 2 − 1) + ( n2 2 − 1) + · · · + ( nt 2 − 1) = n 2 − t by Lemma 2.5. Since p(Γ) = 0 and θ(Γ) = t, the equality i+(Γ) = n−p(Γ) 2 − θ(Γ) holds. Conversely, let Γ be a signed graph sa… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

13 extracted references · 11 canonical work pages

  1. [9]

    X.B. Ma, D. Wong, F.L. Tian, Nullity of a graph in terms of the dimension of cycle space and the number of pendant vertices, Discrete Applied Mathematics, 215 (2016) 171-176. https://doi.org/10.1016/j.dam.2016.07.010

  2. [4]

    F. Duan, Y . H. Yang, Triangle-free signed graphs with small negative inertia index, Discrete Applied Mathematics, 357 (2024) 135-142. https: //doi.org/10.1016/j.dam. 2024.06.012

  3. [1]

    Open problems in the spectral theory of signed graphs

    F. Belardo, S. Cioab˘ a, J. Koolen, J.F. Wang, Open problem in the spectral theory of signed graphs, Art Discrtete Applied Mathematics, 1 (2018) 2-24. https: //doi.org/ 10.48550/ arXiv.1907.04349

  4. [2]

    Cvetkovi ´c, M

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

  5. [3]

    Devadas Acharya, Spectral criterion for cycle balance in networks, Journal of Graph Theory, 4 (1) (1980) 1-11

    B. Devadas Acharya, Spectral criterion for cycle balance in networks, Journal of Graph Theory, 4 (1) (1980) 1-11. https://doi.org/10.1002/jgt.3190040102

  6. [6]

    Harary F .On the notion of balance of a signed graph, The Michigan Mathematical Journal,1953,2(2):143-146

  7. [7]

    Haemers, H

    W.H. Haemers, H. Topcu, On signed graphs with at most two eigenvalues unequal to ±1.[J]. Linear Algebra and its Applications, 670 (2023) 68-77. https://doi.org/10.1016/ j.laa.2023.04.001

  8. [8]

    H. Ma, W. Yang, S. Li, Positive and negative inertia index of a graph, Linear Algebra and Its Applications, 438 (2013) 331-341. https://doi.org/10.1016/j.laa.2012.07.014

Show all 13 references
  1. [10]

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

    A. Torga ˇsev, On graphs with a fixed number of negative eigenvalues, Discrete Math- ematics, 57 (1985) 311-317. https://doi.org/10.1016/0012-365X(85)90184-0

  2. [12]

    G. H. Yu, L. H. Feng, Q. W. Wang, Bicyclic graphs with small positive index of iner- tia, Linear Algebra and its Applications, 438 (2013) 2036-2045. https: //doi.org/10.10 16/j.laa.2012.09.031

  3. [13]

    G.H. Yu, X.D. Zhang, L.H. Feng, The inertia of weighted unicyclic graphs, Linear Algebra and its Applications, 44(2014) 130-152. https: //doi.org/10.1016/j.laa .2014.01.023

  4. [14]

    G.H. Yu, L.H. Feng, Q.W. Wang, A. Ili´c, The minimal positive index of inertia of signed unicyclic graphs, Ars Combinatoria, 117(2014) 245-255

  5. [15]

    Shang Y .On the Structural Balance Dynamics Under Perceived Sentiment, Bulletin of the Iranian Mathematical Society,2020,46(3):717-724

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.