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 →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
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$.
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
- 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.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
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)
- [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.
- [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)
- [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'.
- [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'.
- [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.
- [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.
- [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
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
assumptions (3)
- standard math Interlacing Theorem (Theorem 2.1, cited from Cvetković et al.)
- domain assumption Pendant vertex deletion formula (Lemma 2.2, cited from [13])
- domain assumption Inertia of signed cycles and paths (Lemma 2.5, cited from [12,13,14])
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
Reference graph
Works this paper leans on
-
[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
-
[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
doi:10.1016/j.dam 2024
-
[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
work page Pith review arXiv doi:10.48550/arxiv.1907.04349 2018
-
[2]
D. Cvetkovi ´c, M. Doob, H. Sachs, Spectra of Graphs: Theory and Application. Aca- demic Press, New York, 1980. 12
work page 1980
-
[3]
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]
Harary F .On the notion of balance of a signed graph, The Michigan Mathematical Journal,1953,2(2):143-146
work page 1953
-
[7]
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
work page 2023
-
[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
-
[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
1985 doi
-
[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
2013
-
[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
2014 doi
-
[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
2014
-
[15]
Shang Y .On the Structural Balance Dynamics Under Perceived Sentiment, Bulletin of the Iranian Mathematical Society,2020,46(3):717-724
2020
Reviewed August 6, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.