← All papers
First page of Counterexamples, Spectral Obstructions, and Deletion Stability for WOW-284

Counterexamples, Spectral Obstructions, and Deletion Stability for WOW-284

Samuil Petkov

math.CO Jul 29, 2026 · v1 math.SP
Lean 4.31 kernel-checks the 50-vertex Hoffman–Singleton counterexample, finite spectral certificates at orders 38–42, and the analytic LP optimum for all k≥4.
WOW-284 asserts that the minimum dual degree of every connected graph of order at least three and girth at least five does not exceed the negative of its least distance eigenvalue. We refute it with exact counterexamples of orders $38,39,40,42$, and $50$, and develop a structural theory of the failure. For a connected $k$-regular graph of girth at least five and diameter three, we prove $δ^*(G)+λ_{\min}(D(G))=2k-2-\max_{θ\ne k}(θ+1)^2$. Here $θ$ ranges over the nonprincipal adjacency eigenvalues. We further prove that every regular strict counterexample has degree at least six and diameter at most four, while diameter four forces degree at least ten. We solve the associated one-variable nonbacktracking linear program exactly, including optimizer rigidity. For regular strict counterexamples of diameter three, the optimizer yields a positive-semidefinite slack matrix whose integral excess gives the stronger bound $|V(G)|\le\left\lfloor 3(k+2)^2(k^2+3)/(18k+41)\right\rfloor$; this follows from a three-to-one quantization theorem for the integral excess. The slack matrix's principal minors also recover local cycle constraints. In particular, regular degree-six counterexamples have order at most $50$, and at the degree-six, order-$50$ boundary the associated signed complement is necessarily disconnected. We determine the distance spectra of one- and two-vertex punctures of Moore graphs and establish a uniform deletion-stability bound: every deletion of at most five vertices from the Hoffman–Singleton graph remains a strict counterexample, whereas an explicit six-vertex deletion does not. All theorem-level computations use exact arithmetic. Lean 4.31 kernel-checks the explicit $50$-vertex Hoffman–Singleton counterexample at graph level, finite spectral certificates at orders $38,39,40,42$, and the analytic LP optimum and rigidity for every integer $k\ge4$.

WOW-284 conjectures that for connected graphs of order at least three and girth at least five, the minimum dual degree does not exceed the negative of the least distance eigenvalue. The conjecture's validity and the structure of any failures were open.

Exact counterexamples of orders 38, 39, 40, 42, and 50 are constructed and a structural theory of failure is developed. For regular graphs of girth at least five and diameter three, a score formula relating dual degree, least distance eigenvalue, and nonprincipal adjacency eigenvalues is proved, along with degree and diameter obstructions. A one-variable nonbacktracking linear program is solved exactly, yielding order bounds and optimizer rigidity, and deletion stability of Moore-graph punctures is analyzed. Lean 4.31 kernel-checks the explicit 50-vertex graph-level counterexample, the finite spectral certificates, and the analytic LP optimum and rigidity for every integer k≥4.

The conjecture is refuted with explicit counterexamples. Every regular strict counterexample has degree at least six and diameter at most four, with diameter four forcing degree at least ten; regular degree-six counterexamples have order at most 50. Deleting up to five vertices from the Hoffman–Singleton graph preserves the strict counterexample property, while an explicit six-vertex deletion does not.