← All papers
First page of Subcubic graphs without eigenvalues in $(-1, 1)$

Subcubic graphs without eigenvalues in $(-1, 1)$

Shenwei Huang, Zilin Jiang

math.CO Jan 4, 2026 · v3
The structural theorems (2.8, 2.14, 2.15) and supporting lemmas are formalized in Lean 4 with AI assistance, and the Lean source is included as arXiv ancillary files.
Guo and Royle recently classified the connected cubic graphs without eigenvalues of their adjacency matrix in the open interval $(-1, 1)$, and raised the question of extending their classification to graphs of maximum degree at most $3$. Together with their cubic classification, our result fully answers this question by characterizing all connected subcubic graphs that are not cubic and have no eigenvalues in $(-1,1)$. We show that exactly two infinite families and seven sporadic examples occur, and that every sporadic graph has at most $18$ vertices. To obtain this complete classification, we build a bridge between spectral graph theory and structural graph theory for graphs whose adjacency matrices, after selected diagonal entries are changed to $-1$, have smallest eigenvalue at least $-2$. This generalizes the classical theorem of Cameron, Goethals, Seidel and Shult for graphs with smallest eigenvalue at least $-2$. As a consequence, we prove that $(-1,1)$ is a maximal spectral gap set for the class of connected subcubic graphs. Guo and Royle, answering a question of Kollár and Sarnak, established this maximality for connected cubic graphs. Our result generalizes their conclusion to the subcubic setting.

Guo and Royle classified the connected cubic graphs with no adjacency eigenvalues in (-1,1) and asked whether the classification extends to subcubic graphs. The open case is connected subcubic graphs that are not cubic.

Such a graph H has no eigenvalues in (-1,1) exactly when A_H^2 - I is positive semidefinite. This condition is restated in terms of rooted distance-two multigraphs, where roots mark vertices of degree 2, and their modified adjacency matrices. The resulting theory generalizes the Cameron–Goethals–Seidel–Shult theorem on graphs with smallest eigenvalue at least -2. The cases are bipartite graphs of girth 4, bipartite graphs of girth at least 6 (handled via valid triangle-edge decompositions), and non-bipartite graphs (handled via bipartite doubles). The structural theorems and lemmas were formalized in Lean 4 using Codex with an OpenAI GPT model as an independent check.

Exactly two infinite families (HJ_n and HJ'_n) and seven sporadic graphs occur, and each sporadic graph has at most 18 vertices. As a consequence, (-1,1) is a maximal spectral gap set for connected subcubic graphs. The Lean project builds and is provided as ancillary files.