Pith. sign in

REVIEW 2 major objections 5 minor 9 references

Cubic graphs with no eigenvalues in the interval (-2,0)

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

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read This paper establishes a complete classification of cubic graphs with no eigenvalues in the open interval (−2,0): they are exactly one infinite family X(n) and five sporadic graphs.

desk verdict Real classification result, but the girth-5 proof depends on an undocumented computer enumeration that needs to be supplied before the paper is fully reproducible. read the letter →

arxiv 2506.05861 v1 pith:SSJAKEF2 submitted 2025-06-06 math.CO

Krystal Guo , Gordon F. Royle This is my paper
classification math.CO MSC 05C5005C75
keywords cubicgraphsspectralgapeigenvaluespositivesemidefinitematrixprincipalminorsgirthPetersengraphTutte8-cage
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

The paper sets out to identify every cubic (3-regular) graph whose adjacency spectrum avoids the open interval (−2,0). Its claim is a complete list: one infinite family X(n) on 6n vertices for n ≥ 2, together with five sporadic graphs — the 3-prism, K3,3, the Petersen graph, the dodecahedron, and Tutte's 8-cage. This matters because (−2,0) is one of only two maximal spectral gap intervals of length 2 for cubic graphs, and a complete classification converts a known gap into a sharp boundary. The proof shows that any such graph must have a highly constrained local structure around a shortest cycle, then settles each possible girth by hand or, for girth five, with a computer-assisted case analysis.

What carries the argument

The key object is M(G) = A(G)(A(G) + 2I), whose eigenvalues are λ(λ+2) for eigenvalues λ of the adjacency matrix A(G). A cubic graph avoids eigenvalues in (−2,0) exactly when M is positive semidefinite, and a matrix is positive semidefinite exactly when every principal minor is nonnegative. The proof combines this with a combinatorial reading of M's entries (diagonal 3; off-diagonal 2 + common neighbours for adjacent vertices, number of common neighbours otherwise) and with the corona Cor(C) of a girth cycle, the 2g-vertex subgraph formed by the cycle and the unique third neighbour of each cycle vertex. Forbidden configurations — subsets T whose principal submatrix M_TT has negative determinant — progressively restrict the corona, and each possible girth is eliminated or forced to one of the listed graphs.

What would settle it

Independently enumerate, under the stated degree and girth constraints, all strong-open-neighbourhood subgraphs eS attached to the corona of a 5-cycle, and check positive semidefiniteness of M_SS for each: if fewer or more than 13 survive — or if any survivor other than X1 and X7 eventually forces a graph — the classification fails. Alternatively, search cubic graphs on 28 to 30 vertices for one with no eigenvalues in (−2,0) that is not in the listed family.

Watch

Extended reading notes

Core claim

The central claim is Theorem 1.1: a cubic graph G has no eigenvalues in (−2,0) if and only if G is isomorphic to X(n) for some n ≥ 2, or G is the 3-prism K3□K2, K3,3, the Petersen graph, the dodecahedron, or Tutte's 8-cage. The proof's engine is the matrix M = A(A+2I): since the map λ ↦ λ(λ+2) sends (−2,0) to negative values, having no eigenvalues there is equivalent to M being positive semidefinite. Positive semidefiniteness is detected by principal minors, so the argument finds small subsets of vertices whose M-principal-submatrix has negative determinant, ruling out whole classes of local configurations. Around a shortest cycle (the corona), these constraints force the structure to snap together into the listed graphs, girth by girth.

Load-bearing premise

The classification for girth five depends on an asserted computer enumeration of possible extensions of a 5-cycle corona ('a short computation shows that all but 13 choices are ruled out') that is not documented in the paper; if that enumeration is wrong or incomplete, the girth-5 case is not established.

Editorial extensions

If this is right

  • If G is cubic with no eigenvalues in (−2,0), then its girth is 3, 4, 5, or 8; girths 6, 7, and ≥9 are impossible.
  • The only cubic graphs of girth 3, 4, 5, or 8 in the class are, respectively, the 3-prism; K3,3 or X(n); the Petersen graph or the dodecahedron; and Tutte's 8-cage.
  • Every graph in the infinite family X(n) also avoids the two larger intervals (−3, (−1−√17)/2) and ((−1+√17)/2, 2), so the interval (−2,0) is not a maximal spectral gap set.
  • The classification was checked computationally for all cubic graphs on up to 26 vertices, over 2 billion graphs, using exact integer arithmetic.

Reading between the lines

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

  • If the classification is right, then for every cubic graph outside the listed ones there is an explicit small submatrix of A(A+2I) with negative determinant, giving a finite certificate — independent of spectral computation — that the graph has an eigenvalue in (−2,0).
  • The same block-circulant determinant method used for X(n) could probe neighbouring intervals with rational endpoints, since the technique does not depend on the specific value −2.
  • The asserted but undocumented girth-5 enumeration is the single point where an independent check would be most valuable; publishing the full list of the 13 surviving subgraphs would make the proof fully reproducible.
Share X Bluesky LinkedIn Reddit HN

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 claims a complete classification of cubic graphs with no eigenvalues in the open interval (-2,0). The main theorem states that the only such graphs are the infinite family X(n) for n >= 2 and five sporadic graphs: the 3-prism, K_{3,3}, the Petersen graph, the dodecahedron, and Tutte's 8-cage. The proof uses the matrix M = A(A+2I), which must be positive semidefinite, and then analyzes the local structure around a shortest cycle separately for each possible girth. For girths 3, 4, 6, 7, 8, and at least 9, the arguments are explicit determinant computations on small principal submatrices. For girth 5, the authors reduce the possibilities for the subgraph eS to 13 cases by a computer enumeration that is asserted but not documented, and then rule out all but two of those cases by hand.

Significance. If the classification is correct, it resolves the spectral gap interval (-2,0) for cubic graphs completely, complementing the authors' earlier classification for (-1,1) and providing the only other known length-2 integer-endpoint spectral gap interval. The hand-checkable parts of the proof are explicit: the determinant computations are small and verifiable, and the characteristic polynomial of the infinite family X(n) is derived in closed form using block-circulant matrices. However, the girth-5 case rests on a computer enumeration that is not described in enough detail to be verified from the paper, and the computational check in Section 7.1 covers only graphs up to 26 vertices. The central classification is therefore not currently fully verifiable from the manuscript alone.

major comments (2)
  1. [Section 6, Girth five] The assertion 'A short computation shows that all but 13 choices for eS are ruled out by this requirement' is load-bearing for Theorem 6.1, but the computation is not described. The paper does not specify the search space (how many new vertices may be added, how adjacencies to C5 ∘ K1 are generated, how the degree and girth constraints are enforced, or how the positive-semidefinite test is implemented), nor does it provide code or an explicit list of all enumerated candidates. Because Lemmas 6.2-6.4 and the final dichotomy in the proof of Theorem 6.1 depend on the completeness of the resulting list of 13 subgraphs X0,...,X12, the girth-5 classification is not independently verifiable from the manuscript.
  2. [Section 7.1, Computational Note] The verification for all cubic graphs on up to 26 vertices is a useful sanity check, but it does not cover the infinite family X(n) for n >= 5 (which has 6n > 26 vertices) or any other cubic graph of girth 5 with more than 26 vertices. It therefore cannot substitute for a documented proof of exhaustiveness in the girth-5 enumeration. The authors should either supply the enumeration code and output, or replace the asserted computation with a hand-checkable argument for the completeness of the 13 surviving cases.
minor comments (5)
  1. [Section 3, spectra of sporadic graphs] The displayed spectrum of the dodecahedron, sp(D) = {3, sqrt(5)^(3), 0^(4), -2^(4), -sqrt(5)^(3), 3}, is incorrect: it lists 3 twice and omits the eigenvalue 1 with multiplicity 5. The correct spectrum is {3, sqrt(5)^(3), 1^(5), 0^(4), -2^(4), -sqrt(5)^(3)}. This does not affect the argument, since 1 is not in (-2,0), but it should be corrected.
  2. [Section 4.1, Girth three] In the proof of Lemma 4.2, the reference 'By Theorem 4.1' should be 'By Lemma 4.1'. Similarly, in Lemma 4.3 the reference 'Theorem 4.2' should be 'Lemma 4.2'.
  3. [Section 6, proof of Lemma 6.2] The phrase 'degree one in eC' should be 'degree one in eS'. In addition, the notation 'M_wu = 0 for all w in {w0,w1} and v in {u1,u2,u3,u4}' would be clearer as 'M_{w v} = 0'.
  4. [Section 6, proof of Theorem 6.1] The sentence 'by Theorems 6.2 to 6.4' should refer to Lemmas 6.2 to 6.4, since those results are labeled as lemmas.
  5. [Section 6, proof of Lemma 6.3] The statement that 'there can be no edge or 2-path between these two vertices by the girth constraint' is correct but would benefit from a one-sentence justification: an edge between v01 and v04 would create a triangle v0-v01-v04-v0, and a 2-path would create a 4-cycle, both of which are forbidden in a graph of girth 5.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the classification is derived from the PSD condition via local structural analysis; the only caveat is an asserted finite enumeration in the girth-5 case, which is a proof gap, not a circular step.

full rationale

The paper's derivation chain is self-contained and non-circular. The 'if' direction of Theorem 1.1 is established by explicit spectra for the five sporadic graphs (Section 3) and by the characteristic polynomial of X(n) (Theorem 3.2), which is computed from the block-circulant adjacency matrix. The 'only if' direction proceeds by girth: for girths 3, 4, 6, 7, 8 and ≥9, the paper exhibits explicit principal submatrices of M = A(A+2I) with negative determinant, forcing an eigenvalue in (−2,0) via Lemma 2.1. These determinants are given in closed form and depend only on the local corona structure, not on the target classification. For girth 5, the argument relies on a finite enumeration of possible strong-neighbourhood subgraphs eS, asserted as 'A short computation shows that all but 13 choices for eS are ruled out by this requirement' (Section 6). This is an asserted computation, not a fitted parameter, and it is not equivalent to the theorem's conclusion; it is a gap in documented proof rather than circular reasoning. The self-citations to the authors' earlier work [6] concern the general technique of using (A(G) + cI)(A(G) + dI) semidefiniteness, not the classification result itself, so no claim here is justified solely by a self-citation. Thus no step reduces by construction to its own input; circularity score 0.

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

No free parameters are introduced. The proof relies on standard linear algebra facts (principal minor test for positive semidefiniteness, interlacing, block-circulant determinant formula), the known uniqueness of Tutte's 8-cage, and a computer enumeration in the girth 5 case that is asserted but not fully documented.

assumptions (5)
  • standard math A matrix is positive semidefinite iff all its principal minors are non-negative
    Used throughout Section 4 to rule out subgraphs by finding principal submatrices of M with negative determinant.
  • standard math Interlacing theorem for principal submatrices
    Used in Lemma 2.1 to bound eigenvalues of A from eigenvalues of M.
  • standard math Block-circulant determinant formula
    Used in Theorem 3.1 to compute the characteristic polynomial of X(n).
  • domain assumption Tutte's 8-cage is the unique cubic graph of girth 8 on 30 vertices
    Used in Section 6.3 to identify the constructed 30-vertex graph as Tutte's 8-cage; this is a known result cited implicitly.
  • ad hoc to paper The girth 5 computer enumeration produces exactly the 13 subgraphs X0..X12
    Section 6 states 'A short computation shows that all but 13 choices for eS are ruled out', but the program and enumeration details are not provided; the proof for girth 5 depends on this.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Cubic graphs with no eigenvalues in the interval (-2,0)." pith.science (2026). https://pith.science/paper/SSJAKEF2

@misc{pith2026250605861,
  author       = {Pith},
  title        = {Pith review of: Cubic graphs with no eigenvalues in the interval (-2,0)},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/SSJAKEF2}},
  note         = {Machine review of arXiv:2506.05861}
}
abstract

We give a complete characterisation of the cubic graphs with no eigenvalues in the interval $(-2,0)$. There is one thin infinite family consisting of a single graph on $6n$ vertices for each $n \geqslant 2$, and five ``sporadic'' graphs, namely the $3$-prism $K_3 \mathbin{\square} K_2$, the complete bipartite graph $K_{3,3}$, the Petersen graph, the dodecahedron and Tutte's $8$-cage. The proof starts by observing that if a cubic graph has no eigenvalues in $(-2,0)$ then its local structure around a girth-cycle is very constrained. Then a separate case analysis for each possible girth shows that these constraints can be satisfied only by the known examples. All but one of these case analyses can be completed by hand, but for girth five there are sufficiently many cases that it is necessary to use a computer for the analysis.

Figures

Figures reproduced from arXiv: 2506.05861 by the authors.

Figure 1
Figure 1. The building block for X(n) spectral gap sets and maximal spectral gap intervals (i.e., where I is an open interval). Among numerous other results, they showed that (−1, 1) and (−2, 0) are maximal spectral gap intervals and that any spectral gap interval for cubic graphs has length at most 2. (We note that Guo and Mohar [5] had previously shown that (−1, 1) is a spectral gap interval, but with a different infinite f… view at source ↗
Figure 2
Figure 2. X(5) has five gadgets connected in a cyclic fashion Theorem 1.1. A cubic graph G has no eigenvalues in (−2, 0) if and only if G ∼= X(n) for some n ⩾ 2 or G is the 3-prism K3 □ K2, the complete bipartite graph K3,3, the Petersen graph, the dodecahedron, or Tutte’s 8-cage. The remainder of the paper is structured as follows. In Section 2 we establish our terminology and notation and give an overview of the overall str… view at source ↗
Figure 3
Figure 3. Configurations around a triangle unique common neighbour and taking S = {v, w, w′}, we have MSS =   v w w′ v 3 3 1 w 3 3 2 w′ 1 2 3  , (2) which has determinant −3. Therefore M is not positive semidefinite contradicting the hy￾potheses on G. Otherwise, {u ′ , v′ , w′} do form a triangle, and the entire graph is the 3-prism. The “quantitative version” of this lemma is the following: Lemma 4.3. Let τ ′ ≈ −0.201912… view at source ↗
Figures from the paper (19 more)
Figure 4
Figure 4. Figure 4: Corona of a 4-cycle vertices V = {v0, v1, v2, v3} may not be distinct but because G has girth 4 it follows that vi ̸= vi±1. So it may be the case that v0 = v2 and v1 = v3, or (without loss of generality) v0 = v2 but v1 ̸= v3, or that v0 ̸= v2 and v1 ̸= v3. These three …
Figure 5
Figure 5. Figure 5: Configuration around a corona isomorphic to [PITH_FULL_IMAGE:figures/full_fig_p010_5.png]
Figure 6
Figure 6. Figure 6: Graph induced by corona C1. and w3 are distinct and must be non-adjacent (to avoid creating a 4-cycle with corona not isomorphic to C1), leading to the graph shown in the first diagram of [PITH_FULL_IMAGE:figures/full_fig_p012_6.png]
Figure 7
Figure 7. Figure 7: Extending the gadget 6 Girth five This section is dedicated to proving the following: Theorem 6.1. If G is a cubic graph of girth 5 with no eigenvalues in (−2, 0) then G is either the Petersen graph or the dodecahedron. If S is a set of vertices in a graph, then we def…
Figure 8
Figure 8. Figure 8: The corona product C5 ◦ K1 respect the degree and girth constraints. This leaves a long list of graphs as possibilities for Se, but the requirement that MSS be positive semidefinite means that many of these subgraphs simply cannot occur in a graph with no eigenvalues i…
Figure 9
Figure 9. Figure 9: Possibilities for the subgraph Se when S = V (Cor(C5)). 15 [PITH_FULL_IMAGE:figures/full_fig_p015_9.png]
Figure 10
Figure 10. Figure 10: Ruling out X5 and X6 it follows that MT T =             u0 u1 u2 u3 u4 v0 w0 w1 u0 3 2 1 1 2 2 1 1 u1 2 3 2 1 1 1 0 0 u2 1 2 3 2 1 0 0 0 u3 1 1 2 3 2 0 0 0 u4 2 1 1 2 3 1 0 0 v0 2 1 0 0 1 3 2 2 w0 1 0 0 0 0 2 3 1 w1 1 0 0 0 0 2 1 3             …
Figure 11
Figure 11. Figure 11: Ruling out X9 and X11 there can be no edge or 2-path between these two vertices by the girth constraint. Therefore MT T =           u2 u3 v1 v3 v01 v4 v04 u2 3 2 1 1 0 0 0 u3 2 3 0 2 0 1 0 v1 1 0 3 0 2 0 0 v3 1 2 0 3 0 0 0 v01 0 0 2 0 3 0 1 v4 0 1 0 0 0 3 2 …
Figure 12
Figure 12. Figure 12: Cycles whose corona cannot be X7. w12 w23 v23 [PITH_FULL_IMAGE:figures/full_fig_p019_12.png]
Figure 13
Figure 13. Figure 13: The dodecahedron is the only graph that arises [PITH_FULL_IMAGE:figures/full_fig_p019_13.png]
Figure 14
Figure 14. Figure 14: Corona of a 6-cycle in a graph of girth 6. [PITH_FULL_IMAGE:figures/full_fig_p020_14.png]
Figure 15
Figure 15. Figure 15: Corona of a 7-cycle in a graph of girth 7. [PITH_FULL_IMAGE:figures/full_fig_p021_15.png]
Figure 16
Figure 16. Figure 16: Corona of an 8-cycle in a graph of girth 8. [PITH_FULL_IMAGE:figures/full_fig_p022_16.png]
Figure 17
Figure 17. Figure 17: As we will repeatedly be using it, we emphasize that this argument implies that if C is any 8-cycle in G and s and t are antipodal vertices on C, then their neighbours s ′ ∼ s and t ′ ∼ t off C must themselves share a common neighbour. The remainder of the argument is…
Figure 17
Figure 17. Figure 17: Structure induced by an 8-cycle and also not equal to any vertex in {v04, v15, v26, v37} because otherwise G would contain a cycle of length less than 8. Now we will use the argument about antipodal vertices on an 8-cycle, in particular we consider the 8-cycle D = (u0…
Figure 18
Figure 18. Figure 18: A second 8-cycle in the graph v0 u0 w0 v1 u1 w1 v2 u2 w2 v3 u3 w3 u4 v4 w4 v5 u5 w5 v6 u6 w6 v7 u7 w7 v04 v26 v15 v37 [PITH_FULL_IMAGE:figures/full_fig_p024_18.png]
Figure 19
Figure 19. Figure 19: A 28-vertex graph with four vertices of degree two [PITH_FULL_IMAGE:figures/full_fig_p024_19.png]
Figure 20
Figure 20. Figure 20: Tutte’s 8-cage minus one edge that is Tutte’s 8-cage minus a single edge, as depicted in [PITH_FULL_IMAGE:figures/full_fig_p025_20.png]
Figure 21
Figure 21. Figure 21: Configuration in the corona of a 9-cycle [PITH_FULL_IMAGE:figures/full_fig_p026_21.png]

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

9 extracted references · 9 canonical work pages

  1. [1]

    Line graphs, root systems, and elliptic geometry.Journal of Algebra, 43(1):305–327, 1976

    P.J Cameron, J.M Goethals, J.J Seidel, and E.E Shult. Line graphs, root systems, and elliptic geometry.Journal of Algebra, 43(1):305–327, 1976

    work page 1976

  2. [2]

    Cubic Ramanujan graphs.Combinatorica, 12(3):275–285, 1992

    Patrick Chiu. Cubic Ramanujan graphs.Combinatorica, 12(3):275–285, 1992

    work page 1992

  3. [3]

    Fowler and Tomaˇ z Pisanski

    Patrick W. Fowler and Tomaˇ z Pisanski. HOMO-LUMO maps for chemical graphs. MATCH Commun. Math. Comput. Chem., 64(2):373–390, 2010. 27

    work page 2010

  4. [4]

    On the corona of two graphs.Aequationes Math., 4:322–325, 1970

    Roberto Frucht and Frank Harary. On the corona of two graphs.Aequationes Math., 4:322–325, 1970

    work page 1970

  5. [5]

    Large regular bipartite graphs with median eigenvalue 1.Linear Algebra Appl., 449:68–75, 2014

    Krystal Guo and Bojan Mohar. Large regular bipartite graphs with median eigenvalue 1.Linear Algebra Appl., 449:68–75, 2014

    work page 2014

  6. [6]

    Krystal Guo and Gordon F. Royle. Cubic graphs with no eigenvalues in the interval (-1,1), 2024

    work page 2024

  7. [7]

    Expander graphs and their applica- tions.Bulletin of the American Mathematical Society, 43(4):439–561, 2006

    Shlomo Hoory, Nathan Linial, and Avi Wigderson. Expander graphs and their applica- tions.Bulletin of the American Mathematical Society, 43(4):439–561, 2006

    work page 2006

  8. [8]

    Gap sets for the spectra of cubic graphs.Communications of the American Mathematical Society, 1(1):1–38, 2021

    Alicia Koll´ ar and Peter Sarnak. Gap sets for the spectra of cubic graphs.Communications of the American Mathematical Society, 1(1):1–38, 2021

    work page 2021

Show all 9 references
  1. [9]

    The PARI Group.PARI/GP version2.15.5. Univ. Bordeaux, 2024. available from http://pari.math.u-bordeaux.fr/. 28

    2024

Pith tools

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