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

arXiv:2607.27452 · math.CO, math.SP · Submitted 2026-07-29 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Mathematics. The day in mathematics: new theorems, new proofs, and what they open.

Ada: I'm Ada.

Emmy: And I'm Emmy, here with Kolya.

Ada: We're looking at the paper: "Counterexamples, Spectral Obstructions, and Deletion Stability for WOW-284".

Title and authors: Ada: So we're looking at the paper "Counterexamples, Spectral Obstructions, and Deletion Stability for WOW-two hundred eighty-four <ref:2607.27452#pg1,Counterexamples, Spectral Obstructions, and Deletion Stability for WOW-284>." It addresses that initial assertion by saying it's wrong with actual graphs of orders thirty-eight thirty-nine forty forty-two and fifty <ref:2607.27452#pg1,of orders 38, 39, 40, 42 and 50>.

Emmy: It’s about showing that the minimum dual degree isn't always bounded by the negative of the least distance eigenvalue for connected graphs with at least three vertices and girth five. She’s really digging into what causes that failure.

Kolya: So, what's the main story here? Is she just finding more counterexamples, or is there a deeper structural reason why this inequality breaks down?

Ada: It’s not just about finding more examples; she develops a whole structural theory for why these failures happen. She looks at regular graphs with diameter three and girth five, and it ties the failure to how those nonprincipal adjacency eigenvalues are confined within a certain window.

Emmy: That confinement part is key because it gives us an algebraic way to characterize when the inequality fails, linking the spectral properties directly to the local geometry of the graph.

Kolya: So what does that confinement actually mean for someone applying this? Does it tell us anything about how these graphs are built, like if they must have a certain shape?

Ada: It suggests that every regular graph that breaks the rule has a degree of at least six and a diameter of at most four. And for diameter four, the degree has to be at least ten.

Emmy: That's a strong restriction; it narrows down the search space significantly when we look for these counterexamples, because we only have to consider graphs with small diameters or larger degrees.

Kolya: Okay, so if we think about the numbers she gives, like that bound on order n based on degree k and diameter three, what does that tell you about how big these graphs can get?

Ada: She solves a one-variable nonbacktracking linear program exactly to find the ceiling for those diameter three graphs as B k equals k plus two times k squared plus three to the sixth power.

Emmy: That exact ceiling is important because it tells us the absolute limit on how many vertices a graph with degree k can have if it's still failing that inequality in that specific way.

Title and authors: Kolya: And then there’s this integral excess calculation, where she finds a stronger bound on n based on the quantity r, which is defined using k and n. Is that just a tighter version of the previous bound?

Ada: It is tighter because it comes from applying a three to one quantization theorem to that integral excess, which gives us n less than or equal to three times r.

Emmy: That connects the continuous spectral condition directly back to the discrete count of vertices in a very concrete way, showing how local structure forces global size limitations.

Kolya: So we’ve talked about the main results—the specific orders she found, and these structural bounds for graphs with diameter three—but what about those other parts of this paper?

Ada: There's the analysis on deletion stability. She looks at how robust these counterexamples are when you remove vertices from them, and it turns out that deleting at most five vertices from a Hoffman Singleton graph still leaves a strict counterexample.

Emmy: That suggests there’s some kind of inherent redundancy or structure in these failing graphs, because they don't fall apart just by losing a few points.

Kolya: So if we delete five vertices from that Hoffman Singleton example, does that change the core reason why the original inequality failed?

Ada: It doesn't change it; it confirms that the mechanism causing the failure is stable under small deletions, up to a radius of five vertices. The universal radius for this property is exactly five.

Emmy: That’s a nice structural finding because it shows that these counterexamples aren't fragile things; they have some deep underlying connectivity that resists simple local destruction.

Kolya: What about the other parts, like the distance spectra of punctured graphs? Is she looking at how deleting vertices affects those specific distance measurements?

Ada: She does investigate that too. For one deleted vertex from a degree k Moore graph, she finds the minimum dual degree is k minus one over k, and strictness holds exactly for integers k greater than or equal to five.

Emmy: That’s a very clean result because it gives an exact condition on the degree for those specific punctured structures to maintain that strict inequality.

Kolya: And when you delete two nonadjacent vertices, she gets a characteristic polynomial, which confirms strictness for every realizable integer k greater than or equal to six. That’s quite comprehensive coverage of the deletion stability aspect.

Ada: So we've covered the counterexamples themselves, the structural constraints on degree and diameter, and how stable these structures are under vertex deletion.

Title and authors: Emmy: The main implication is that for a long time, we thought the WOW-two hundred eighty-four inequality held true for all graphs of that type, but this paper shows there are very specific algebraic conditions—related to those nonprincipal eigenvalues—under which it fails <ref:2607.27452#pg1>.

Kolya: It implies that the relationship between the dual degree and that least distance eigenvalue isn't universal; it depends on the specific spectral configuration of the graph, not just its size or girth.

Ada: Exactly. The paper shows that when you have a regular graph with diameter three and girth five, confinement of those eigenvalues to a narrow band around negative one is the precise mechanism driving the failure.

Emmy: It shifts our focus from looking for larger graphs that might be counterexamples to understanding the specific spectral geometry—that confinement—that forces them to exist.

Kolya: So what's left for us? Does this paper suggest any way forward for other spectral inequalities, or is this just a deep dive into one specific problem?

Ada: It opens up questions about how optimal polynomial certificates relate to local constraints, and whether small global defects force the graph structure to be very close to some kind of structured algebraic model.

Emmy: And it makes us wonder which spectral arguments actually survive when we start losing things like homogeneity or commutativity, which is something that's always tricky in these kinds of problems.

Kolya: It’s a lot of detail, but I think the most important thing is seeing how these exact computations—the exact arithmetic and formal verification using Lean four point three one—pin down the boundaries so tightly <ref:2607.27452#pg2>.

Ada: Those exact computations are what make this work; they give us that rigor we need to trust when we're dealing with spectral inequalities, especially when the results involve such precise bounds like B k equals k plus two times k squared plus three to the sixth power.

Emmy: It really shows that these results aren't just heuristic guesses; they are hard, verifiable facts about graph structure and eigenvalues.

Kolya: So to wrap up on "Counterexamples, Spectral Obstructions, and Deletion Stability for WOW-two hundred eighty-four" it’s a detailed map showing exactly where the inequality breaks down in terms of graph size and shape <ref:2607.27452#pg1,Counterexamples, Spectral Obstructions, and Deletion Stability for WOW-284>.

Ada: It is a very rigorous paper that gives us concrete examples of failure and precise structural limits on those failures.

Emmy: It pushes us to think more about the interplay between the distance spectrum, the dual degree, and spectral confinement in these types of highly symmetric graphs.

The paper's summary: Ada: So, this paper is essentially taking that original statement about the minimum dual degree not exceeding negative least distance eigenvalue and saying, "Hold on, we found graphs where that's false."

Emmy: Exactly. They found concrete counterexamples for orders thirty-eight, thirty-nine, forty, forty two and fifty. They aren't just theoretical ideas; they’re actual graphs that break the rule you mentioned at the beginning.

Kolya: So what’s the bigger picture here? Is this just about finding more examples, or is there a deeper reason why this spectral relationship breaks down in these specific graph structures?

Ada: They developed a whole structural theory for *why* it fails. For regular graphs with diameter three and girth five, they show the failure happens because every nonprincipal adjacency eigenvalue gets stuck in a very narrow range.

Emmy: That confinement is the key. It links the spectral property directly to how tightly packed those eigenvalues are, which dictates the graph's local geometry.

Kolya: So what does that confinement tell us about these graphs? Does it force them into a specific shape or structure?

Ada: It tells us that any regular graph that fails this test must have a degree of at least six and its diameter can be at most four. And if the diameter is four, the degree has to be at least ten.

Emmy: That’s a major restriction because it narrows down where we have to look for these counterexamples, focusing on graphs with small diameters or high degrees.

Kolya: Okay, so we've seen the specific examples and the structural limits for diameter three graphs. What about those other parts of this paper? The deletion stuff?

Ada: They looked at how robust these counterexamples are when you remove vertices from them. It turns out that removing at most five vertices from a Hoffman Singleton graph still leaves a strict counterexample.

Emmy: That suggests there’s an underlying stability in these failing structures; they don't fall apart just by losing a few points. The universal radius for this property is exactly five, which is pretty specific.

Kolya: Does that mean the original reason the inequality failed still holds after we delete those five vertices?

Ada: It doesn't change it at all; it confirms that the mechanism causing the failure is stable under small deletions, up to a radius of five vertices. The proof is solid because they used exact arithmetic and formal verification.

Emmy: It’s important that this isn't just some approximation; they certified the fifty-vertex Hoffman Singleton counterexample using tools like Lean four point three one. That gives us real confidence in these results.

Kolya: So to sum up, this paper shows that the failure of the original inequality isn't random; it’s driven by specific spectral confinement and structural constraints on graph size and diameter, and these failing structures are surprisingly stable under local vertex deletion.

Ada: Precisely. It shifts our view from just hunting for larger counterexamples to understanding the precise algebraic conditions—the confinement—that force them to exist in the first place.

Emmy: It opens up new questions about how optimal polynomial certificates relate to local constraints, and whether those small global defects force a graph structure to be very close to some kind of structured algebraic model.

The paper's improvements: Tom: So we're looking at how this paper suggests they can make these counterexamples even more precise or robust for future work, right?

Ada: Well, they’re pushing to show that the structural constraints they found are not just a coincidence but are fundamental to the problem. They want to see if those bounds hold even when we move away from regular graphs.

Emmy: They're looking at how much flexibility there is in these spectral confinement conditions. They want to know if there's any room for deviation before the inequality definitely breaks again.

Kolya: If they can tighten those structural bounds, does that help us predict whether we’ll find more counterexamples, or just confirm that the current ones are the most extreme?

Ada: They are focusing on making those exact number bounds—like the ceiling B k equals k plus two times k squared plus three to the sixth power—even more rigid. They want to prove that equality cases happen only for very specific numbers.

Emmy: That’s about proving that when things hit the boundary of what works, it has a very strict, almost rigid structure underlying it. They are using tools like integral slack matrix analysis to get those precise limits.

Kolya: I wonder if these tighter bounds mean we can actually rule out certain families of graphs entirely, or if we’re just getting better at counting the ones that fit the criteria.

Ada: They’re trying to show that for specific parameters, like when k is ten three and n is one eight five two twenty zero, an exact equality case exists. That identifies a unique arithmetic parameter classification for those boundary conditions.

Emmy: It means they’ve mapped out the entire edge of the mathematical landscape for these graphs; everything outside that map is confirmed to follow different rules.

Kolya: So what's the bigger implication if we can confirm these boundaries so tightly? Does it change how we approach spectral inequalities in general, or just for this specific type of graph?

Ada: It points toward a broader question about how optimal polynomial certificates relate to local constraints. They want to see if small defects—like losing a few vertices—force the graph structure to be very close to some kind of structured algebraic model.

Emmy: If they can show that any deviation from this confined state leads immediately back into one of those structured models, that’s powerful structural information for algebraic geometry.

Kolya: It sounds like they are moving from just proving something is false to proving exactly *why* it must be true in certain contexts.

Ada: Exactly. They are trying to bridge the gap between a simple spectral inequality and the complex geometric reality of graph structure, using these exact computations to pin down every possible configuration.

Conclusion: Ada: So we're wrapping up this deep dive into "Counterexamples, Spectral Obstructions, and Deletion Stability for WOW-two hundred eighty-four." Essentially, we saw how specific spectral confinement forces graphs to behave in ways that break the original inequality.

Emmy: Right. The big picture is that this isn't just about finding more examples of failure; it's about understanding the precise algebraic geometry—the spectral confinement—that *causes* them to exist in these specific graph structures.

Kolya: From a probabilistic standpoint, the paper shows us that if you look at these counterexamples, the tail behavior is governed by very tight constraints on those nonprincipal eigenvalues. The constants survive because the structure is so rigid.

Ada: It changes how we think about spectral inequalities in general because it demonstrates that small global defects can have massive local implications for graph structure.

Emmy: Yeah, it pushes us to look at what happens when you perturb a system slightly, and see if the underlying algebraic model stays intact or falls apart.

Kolya: If we can nail down these stability bounds, it gives us a better framework for predicting where these spectral relationships might hold true in other mathematical systems.

Ada: It’s a lot of detail, but the precision they bring to certifying those fifty-vertex counterexamples using exact computation is what makes this work so important.

Emmy: They’ve laid down some very strong constraints on diameter and degree, which really helps us visualize where these failures can even happen.

Kolya: So while we're done with the specifics of this paper, it leaves us wondering if there are other types of spectral arguments that survive when things get messy and lose their symmetry.

SAMUIL PETKOV

math.CO, math.SP

Submitted: 2026-07-29

Updated: 2026-11-15

Comments: 44 pages. Exact computations and Lean 4.31 certificates

Code: https://github.com/SamPetkov/wow284

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 80/100

The gist: 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…

Key concepts

Minimum Dual Degree
This is a graph property related to how many edges are needed in a specific dual structure of the graph. The paper uses this metric, comparing it to the least distance eigenvalue, to test the original theorem. If this degree is smaller than the negative of the eigenvalue, WOW-284 holds.
Spectral Confinement
This describes a condition where all nonprincipal eigenvalues (except for a few special ones) of a regular graph are forced to lie within a very narrow, specific range on the complex plane. For graphs failing the theorem, this confinement is key to proving why they are counterexamples.
Deletion Stability
This concept investigates how robust these counterexamples are when vertices are removed from them. The paper shows that many known counterexamples, like those derived from the Hoffman–Singleton graph, remain strict failures even after deleting up to five vertices, establishing a universal radius of five for this stability.
Adjacency Eigenvalues
These are the eigenvalues associated with the graph's adjacency matrix. The paper focuses on nonprincipal eigenvalues—those that are not simply related to the graph's degree—to determine if they fall within specific spectral intervals, which is crucial for classifying graphs as counterexamples.

Terminology

Summary

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 <ref:2607. p. 0

Where the paper says it

COUNTEREXAMPLES, SPECTRAL OBSTRUCTIONS, AND DELETION STABILITY FOR WOW-284 SAMUIL PETKOV Abstract. 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.

27452#pg2>

Refutation and Structural Theory

The paper refutes WOW-284 with exact counterexamples for orders 38, 39, 40, 42, and 50 and develops a structural theory of the failure. For a connected regular graph of girth at least five and diameter three, the authors prove that the sum of the dual degree and the minimum distance eigenvalue equals a specific expression involving nonprincipal adjacency eigenvalues. p. 0

Where the paper says it

For a connected 𝑘-regular graph of girth at least five and diameter three, we prove 𝛿 ∗ (𝐺) + 𝜆min (𝐷(𝐺) ) = 2𝑘 − 2 − max 𝜃≠𝑘 ( 𝜃 + 1) 2 . Here 𝜃 ranges over the nonprincipal adjacency eigenvalues.

Furthermore, every regular strict counterexample must have a degree of at least six and a diameter at most four, with diameter four forcing a degree of at least ten. p. 0
Where the paper says it

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.

Bounds on Counterexamples

The analysis establishes several key bounds for regular strict counterexamples. For connected regular graphs of girth at least five and diameter three, strict failure is equivalent to confining every nonprincipal adjacency eigenvalue to the open interval (−1 − √2k − 2, −1 + √2k − 2). p. 1

Where the paper says it

Our main conclusions are as follows. • For connected regular graphs of girth at least five and diameter three, strict failure of WOW-284 is equivalent to confinement of every nonprincipal adjacency eigenvalue to the open interval (−1 − √ 2𝑘 − 2, −1 + √ 2𝑘 − 2); see Theorem 3.

The one-variable nonbacktracking linear program yields an exact ceiling for the order of such graphs as B k = (k + 2) (k squared + 3) 6. p. 0
Where the paper says it

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 |𝑉 (𝐺) | ≤ 3(𝑘 + 2) 2 (𝑘 2 + 3) 18𝑘 + 41 ; this follows from a three-to-one quantization theorem for the integral excess.

For regular strict counterexamples of diameter three, the integral excess leads to the bound n ≤ 3(k + 2) 2(k squared + 3) / (18k + 41). p. 0
Where the paper says it

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 |𝑉 (𝐺) | ≤ 3(𝑘 + 2) 2 (𝑘 2 + 3) 18𝑘 + 41 ; this follows from a three-to-one quantization theorem for the integral excess.

The Hoffman-Singleton Case and Deletion Stability

The paper investigates the stability of counterexamples under vertex deletion, finding that every deletion of at most five vertices from the Hoffman–Singleton graph remains a strict counterexample. The universal radius for this property is exactly five, as a six-vertex deletion does not remain strict. p. 1

Where the paper says it

• One-vertex, adjacent-pair, and nonadjacent-pair deletions of Moore graphs admit exact invariant-subspace decompositions for their recomputed distance matrices; see Section 7. • Every deletion of at most five vertices from the Hoffman–Singleton graph remains a strict counterexample, and this universal radius is sharp; see Theorem 8.

Exact Computation and Rigidity

The authors employ exact arithmetic and formal verification using Lean 4.31 to certify the 50-vertex Hoffman–Singleton counterexample. p. 0

Where the paper says it

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.

The analytic arguments are supported by symbolic identities, integral slack matrix constraints, and local cycle certificates that quantify the excess into a three-to-one bound. p. 0
Where the paper says it

For regular strict counterexamples of diameter three, the optimizer yields a positive-semidefinite slack matrix whose integral excess gives the stronger bound |𝑉 (𝐺) | ≤ 3(𝑘 + 2) 2 (𝑘 2 + 3) 18𝑘 + 41 ; this follows from a three-to-one quantization theorem for the integral excess. The slack matrix’s principal minors also recover local cycle constraints.

Equality in the order bound is arithmetically rigid for specific parameters (k, n, r). p. 1
Where the paper says it

Equality in the unrounded inequality is arithmetically rigid: (𝑘, 𝑛, 𝑟) = (103, 185220, 61740); see Corollary 6. The same slack matrix’s 2 × 2 minors yield a general cycle-divisibility sieve and the local degree-six, order-51 contradiction 5𝑁5 = 153 · 11 = 1683, where 𝑁5 denotes the number of 5-cycles.

Classification of Obstructions

The paper concludes that every regular strict counterexample falls into one of three categories: diameter two (a Moore graph), diameter three with spectral confinement, or diameter four with degree at least ten. The analysis also shows that for odd prime fields, constructions based on the coordinate Hoffman–Singleton graph do not yield strict counterexamples. p. 0

Where the paper says it

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.

Distance Spectra of Punctured Graphs

The authors determine the distance spectra of one- and two-vertex punctures of Moore graphs and establish a uniform deletion-stability bound. Specifically, for one deleted vertex from a degree-k Moore graph, the minimum dual degree is k − 1 / k, and the strictness holds exactly for integers k ≥ 5. p. 0

Where the paper says it

A degree-𝑘 Moore graph of diameter two has 𝐴 2 = (𝑘 − 1)𝐼 − 𝐴 + 𝐽, 𝐷 = 2𝐽 − 2𝐼 − 𝐴, and hence 𝛿 ∗ (𝐺) = 𝑘, 𝜆min (𝐷) = − 3 + √ 4𝑘 − 3 2 . The conjecture holds on these graphs exactly for 𝑘 ≤ 3, with equality at 𝑘 = 3, and fails for every realizable 𝑘 > 3.

The analysis of two nonadjacent deleted vertices yields an explicit distance characteristic polynomial that confirms strictness for every realizable integer k ≥ 6. p. 3
Where the paper says it

For degree 7, the multiplicity equations in its proof give adjacency multiplicities 28 at 2 and 21 at −3, and hence the displayed distance spectrum. The exhaustive pair certificate, integer BFS distances, characteristic polynomial, and exact positive-definiteness check are in scripts/verify_exact.

p. 3
Where the paper says it

For degree 7, the multiplicity equations in its proof give adjacency multiplicities 28 at 2 and 21 at −3, and hence the displayed distance spectrum. The exhaustive pair certificate, integer BFS distances, characteristic polynomial, and exact positive-definiteness check are in scripts/verify_exact.

Conclusion on Boundary Cases

The paper explores the boundary cases where equality holds in the spectral inequality, showing that this occurs only for specific parameters (k, n, r) and that no graph exists with an order greater than 50 for degree-six counterexamples. The analysis of the order-50 boundary reveals structural constraints on the signed complement matrix. p. 0

Where the paper says it

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.

Broader Mathematical Questions

The research points toward broader questions concerning how optimal polynomial certificates relate to local constraints and whether small global defects force proximity to structured algebraic models. It also questions which spectral arguments survive when homogeneity or commutativity is lost, such as with degreeweighted operators. p. 1

Where the paper says it

It addresses three structural questions. (1) Which spectral mechanism governs regular counterexamples?

Final Verification

The entire computational process, including kernel checks on finite spectral certificates and exact diagonalization, is verified by independent scripts and. The explicit 50-vertex counterexample is fully formalized in Lean 4. p. 0

Where the paper says it

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.

p. 0
Where the paper says it

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.

31 with Mathlib 4.31. The development pins the exact toolchain and dependency revision in lean/lean-toolchain and lean/lake-manifest. p. 1
Where the paper says it

Our contribution is the specialization to the two-sided WOW window, the exact optimum for the admissible LP class of Section 5, the integral optimal-slack hierarchy, the edge-local cycle certificate, and the deletion theory developed below. We give an exact refutation of WOW-284 and a Lean 4.

p. 1
Where the paper says it

Our contribution is the specialization to the two-sided WOW window, the exact optimum for the admissible LP class of Section 5, the integral optimal-slack hierarchy, the edge-local cycle certificate, and the deletion theory developed below. We give an exact refutation of WOW-284 and a Lean 4.

json. No theorem-level sign or eigenvalue ordering uses floating-point arithmetic. p. 0
Where the paper says it

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.

The exact computations use SymPy and NetworkX and. p. 0
Where the paper says it

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.

The accompanying release archives the labelled graph data, exact rational and polynomial certificates, and finite-orbit records used here. p. 1
Where the paper says it

Precisely specified finite classifications and matrix certificates are treated as computer-assisted proof components. Their exact reproducibility materials are archived with the accompanying release.

The explicit 50-vertex counterexample is fully formalized in Lean 4.31 with Mathlib 4.31. The development pins the exact toolchain and dependency revision in lean/lean-toolchain and lean/lake-manifest.json. It checks the coordinate graph, regularity, the exhaustive common-neighbour certificate, girth five, the adjacency-square and distance-matrix identities, and an exact rational diagonalization with multiplicities. p. 3
Where the paper says it

For degree 7, the multiplicity equations in its proof give adjacency multiplicities 28 at 2 and 21 at −3, and hence the displayed distance spectrum. The exhaustive pair certificate, integer BFS distances, characteristic polynomial, and exact positive-definiteness check are in scripts/verify_exact.

References

[1] Siemion Fajtlowicz. Written on the wall: Conjectures derived on the basis of the program Galatea Gabriella Graffiti. p. 0

Where the paper says it

Aouchiche and Hansen record the following Graffiti conjecture as Conjecture 7. 16 and attribute it to Fajtlowicz’s 1998 Written on the Wall report [1] (see also [2, Conjecture 7.

p. 0
Where the paper says it

Aouchiche and Hansen record the following Graffiti conjecture as Conjecture 7. 16 and attribute it to Fajtlowicz’s 1998 Written on the Wall report [1] (see also [2, Conjecture 7.

Technical report, University of Houston, 1998

[2] Mustapha Aouchiche and Pierre Hansen. Distance spectra of graphs: A survey. p. 0

Where the paper says it

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.

p. 0
Where the paper says it

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.

Linear Algebra and its Applications, 458:301–386, 2014

[3] Aditi Howlader and Pratima Panigrahi. On the distance spectrum of minimal cages and associated distance biregular graphs. p. 1

Where the paper says it

Invariant-subspace decompositions then give exact puncture spectra, while orbitwise positive-definiteness certificates determine the sharp Hoffman–Singleton deletion radius. The distance-polynomial viewpoint is established for minimal cages and distance-polynomial graphs [3, 4].

p. 1
Where the paper says it

Invariant-subspace decompositions then give exact puncture spectra, while orbitwise positive-definiteness certificates determine the sharp Hoffman–Singleton deletion radius. The distance-polynomial viewpoint is established for minimal cages and distance-polynomial graphs [3, 4].

Linear Algebra and its Applications, 636:115–133, 2022

[4] Miquel Àngel Fiol. Quotient-polynomial graphs. p. 1

Where the paper says it

Invariant-subspace decompositions then give exact puncture spectra, while orbitwise positive-definiteness certificates determine the sharp Hoffman–Singleton deletion radius. The distance-polynomial viewpoint is established for minimal cages and distance-polynomial graphs [3, 4].

p. 1
Where the paper says it

Invariant-subspace decompositions then give exact puncture spectra, while orbitwise positive-definiteness certificates determine the sharp Hoffman–Singleton deletion radius. The distance-polynomial viewpoint is established for minimal cages and distance-polynomial graphs [3, 4].

Linear Algebra and its Applications, 488:363–376, 2016

[5] Hiroshi Nozaki. Linear programming bounds for regular graphs. p. 1

Where the paper says it

The distance-polynomial viewpoint is established for minimal cages and distance-polynomial graphs [3, 4]. Nonbacktracking linear-programming bounds are due to Nozaki [5]; related spectral-Moore work appears in [6].

p. 1
Where the paper says it

The distance-polynomial viewpoint is established for minimal cages and distance-polynomial graphs [3, 4]. Nonbacktracking linear-programming bounds are due to Nozaki [5]; related spectral-Moore work appears in [6].

Graphs and Combinatorics, 31(6):1973–1984, 2015

[6] Sebastian M. Cioabă, Jack H Koolen, Hiroshi Nozaki, and Jason R Vermette. p. 1

Where the paper says it

The distance-polynomial viewpoint is established for minimal cages and distance-polynomial graphs [3, 4]. Nonbacktracking linear-programming bounds are due to Nozaki [5]; related spectral-Moore work appears in [6].

Maximizing the order of a regular graph of given valency and second eigenvalue. p. 0
Where the paper says it

COUNTEREXAMPLES, SPECTRAL OBSTRUCTIONS, AND DELETION STABILITY FOR WOW-284 SAMUIL PETKOV Abstract. 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.

p. 0
Where the paper says it

COUNTEREXAMPLES, SPECTRAL OBSTRUCTIONS, AND DELETION STABILITY FOR WOW-284 SAMUIL PETKOV Abstract. 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.

SIAM Journal on Discrete Mathematics, 30(3):1509–1525, 2016

[7] Jörgen Backelin. Sizes of the extremal girth 5 graphs of orders from 40 to 49, 2015

[8] Paul R. Hafner. The Hoffman–Singleton graph and its automorphisms. p. 0

Where the paper says it

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.

p. 0
Where the paper says it

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.

Journal of Algebraic Combinatorics, 18(1):7–12, 2003

[9] M. O’Keefe and Pak-Ken Wong. p. 3

Where the paper says it

The graph 𝑅 is the Anstee–Robertson graph, the unique (6, 5)-cage. O’Keefe and Wong proved minimality, and Wong proved uniqueness [9, 10]; its realization as a Petersen deletion of the Hoffman–Singleton graph also appears in [11, pp.

p. 3
Where the paper says it

The graph 𝑅 is the Anstee–Robertson graph, the unique (6, 5)-cage. O’Keefe and Wong proved minimality, and Wong proved uniqueness [9, 10]; its realization as a Petersen deletion of the Hoffman–Singleton graph also appears in [11, pp.

A smallest graph of girth 5 and valency 6. p. 6
Where the paper says it

Write 5 = 𝜇1 (𝑎) ≥ 𝜇2 (𝑎) ≥ 𝜇3 (𝑎) ≥ 𝜇4 (𝑎). At the smallest feasible value, 𝜒𝑄(5/2) (𝑥) = 1 4 (𝑥 − 5)𝑝5,6 (𝑥), 𝑝5,6 (𝑥) = 4𝑥 3 + 10𝑥 2 − 16𝑥 − 30, 𝑝5,6 (11/6) = −29/27 < 0.

p. 6
Where the paper says it

Write 5 = 𝜇1 (𝑎) ≥ 𝜇2 (𝑎) ≥ 𝜇3 (𝑎) ≥ 𝜇4 (𝑎). At the smallest feasible value, 𝜒𝑄(5/2) (𝑥) = 1 4 (𝑥 − 5)𝑝5,6 (𝑥), 𝑝5,6 (𝑥) = 4𝑥 3 + 10𝑥 2 − 16𝑥 − 30, 𝑝5,6 (11/6) = −29/27 < 0.

Journal of Combinatorial Theory, Series B, 26(2):145–149, 1979

[10] Pak-Ken Wong. On the uniqueness of the smallest graph of girth 5 and valency 6. p. 3

Where the paper says it

The graph 𝑅 is the Anstee–Robertson graph, the unique (6, 5)-cage. O’Keefe and Wong proved minimality, and Wong proved uniqueness [9, 10]; its realization as a Petersen deletion of the Hoffman–Singleton graph also appears in [11, pp.

p. 3
Where the paper says it

The graph 𝑅 is the Anstee–Robertson graph, the unique (6, 5)-cage. O’Keefe and Wong proved minimality, and Wong proved uniqueness [9, 10]; its realization as a Petersen deletion of the Hoffman–Singleton graph also appears in [11, pp.

Journal of Graph Theory, 3(4):407–409, 1979

[12] Edwin R van Dam and Willem H Haemers. Which graphs are determined by their spectrum? p. 3

Where the paper says it

For two 𝑃-vertices in the same layer, the 5-cycle gives no common neighbour when they are adjacent and exactly one when they are nonadjacent; a common 𝑄-neighbour would force their second coordinates to agree. In distinct 𝑃-layers, a common 𝑄-neighbour is determined uniquely by (𝑖 − 𝑖 ′ )𝑘 = 𝑗 ′ − 𝑗.

p. 3
Where the paper says it

For two 𝑃-vertices in the same layer, the 5-cycle gives no common neighbour when they are adjacent and exactly one when they are nonadjacent; a common 𝑄-neighbour would force their second coordinates to agree. In distinct 𝑃-layers, a common 𝑄-neighbour is determined uniquely by (𝑖 − 𝑖 ′ )𝑘 = 𝑗 ′ − 𝑗.

Linear Algebra and its Applications, 373:241–272, 2003

[13] Markus Meringer. Fast generation of regular graphs and construction of cages. p. 1

Where the paper says it

Invariant-subspace decompositions then give exact puncture spectra, while orbitwise positive-definiteness certificates determine the sharp Hoffman–Singleton deletion radius. The distance-polynomial viewpoint is established for minimal cages and distance-polynomial graphs [3, 4].

p. 1
Where the paper says it

Invariant-subspace decompositions then give exact puncture spectra, while orbitwise positive-definiteness certificates determine the sharp Hoffman–Singleton deletion radius. The distance-polynomial viewpoint is established for minimal cages and distance-polynomial graphs [3, 4].

Journal of Graph Theory, 30(2):137–146, 1999

[14] Peter J Cameron, Jean-Marie Goethals, Johan J Seidel, and Ernest E Shult. Line graphs, root systems, and elliptic geometry. p. 4

Where the paper says it

No transitivity or numerical root ordering is used. Fixed graph6, adjacency-list, and edge-list records are provided in data/graphs/.

p. 4
Where the paper says it

No transitivity or numerical root ordering is used. Fixed graph6, adjacency-list, and edge-list records are provided in data/graphs/.

Journal of Algebra, 43(1):305–327, 1976

[15] Dragoš Cvetković, Peter Rowlinson, and Slobodan Simić. Spectral Generalizations of Line Graphs: On Graphs with Least Eigenvalue-2. p. 1

Where the paper says it

Our main conclusions are as follows. • For connected regular graphs of girth at least five and diameter three, strict failure of WOW-284 is equivalent to confinement of every nonprincipal adjacency eigenvalue to the open interval (−1 − √ 2𝑘 − 2, −1 + √ 2𝑘 − 2); see Theorem 3.

p. 1
Where the paper says it

Our main conclusions are as follows. • For connected regular graphs of girth at least five and diameter three, strict failure of WOW-284 is equivalent to confinement of every nonprincipal adjacency eigenvalue to the open interval (−1 − √ 2𝑘 − 2, −1 + √ 2𝑘 − 2); see Theorem 3.

Cambridge University Press, 2004

[16] Jack H Koolen, Kefan Yu, Xiaoye Liang, Harrison Choi, and Greg Markowsky. Non-geometric distance-regular graphs of diameter at least 3 with smallest eigenvalue at least -3. European Journal of Combinatorics, 126:104118, 2025

[17] Gary Greaves, Jack H Koolen, Akihiro Munemasa, Yoshio Sano, and Tetsuji Taniguchi. Edge-signed graphs with smallest eigenvalue greater than-2. p. 1

Where the paper says it

The proofs form two complementary hierarchies. In the obstruction direction, the distance-polynomial identity converts WOW-284 into a shifted adjacency window; scalar trace moments give the one-point LP ceiling; integrality of the optimal slack matrix strengthens the order bound; graph realizability and small Gram minors quantize the remaining excess into the three-to-one bound; edge-local 2 × 2 minors convert the same certificate into cycle counts; and 3 × 3 minors impose the two-path constraints at order fifty, where a signed-root representation forces a nontrivial component decomposition.

p. 1
Where the paper says it

The proofs form two complementary hierarchies. In the obstruction direction, the distance-polynomial identity converts WOW-284 into a shifted adjacency window; scalar trace moments give the one-point LP ceiling; integrality of the optimal slack matrix strengthens the order bound; graph realizability and small Gram minors quantize the remaining excess into the three-to-one bound; edge-local 2 × 2 minors convert the same certificate into cycle counts; and 3 × 3 minors impose the two-path constraints at order fifty, where a signed-root representation forces a nontrivial component decomposition.

Journal of Combinatorial Theory, Series B, 110:90–111, 2015

[20] Marién Abreu et al. A family of regular graphs of girth 5. p. 1

Where the paper says it

Our main conclusions are as follows. • For connected regular graphs of girth at least five and diameter three, strict failure of WOW-284 is equivalent to confinement of every nonprincipal adjacency eigenvalue to the open interval (−1 − √ 2𝑘 − 2, −1 + √ 2𝑘 − 2); see Theorem 3.

p. 1
Where the paper says it

Our main conclusions are as follows. • For connected regular graphs of girth at least five and diameter three, strict failure of WOW-284 is equivalent to confinement of every nonprincipal adjacency eigenvalue to the open interval (−1 − √ 2𝑘 − 2, −1 + √ 2𝑘 − 2); see Theorem 3.

Discrete Mathematics, 308(10):1810–1815, 2008

[21] Aaron Meurer et al. SymPy: Symbolic computing in Python. p. 9

Where the paper says it

Hence the open-window bound is strict. Every symbolic identity, finite slack, tail bound, and equality-nullspace calculation is independently checked by scripts/verify_proof_audit_02_two_sided_lp.

p. 9
Where the paper says it

Hence the open-window bound is strict. Every symbolic identity, finite slack, tail bound, and equality-nullspace calculation is independently checked by scripts/verify_proof_audit_02_two_sided_lp.

PeerJ Computer Science, 3:e103, 2017

[22] Aric A Hagberg, Daniel A Schult, and Pieter J Swart. Exploring network structure, dynamics, and function using NetworkX. p. 9

Where the paper says it

For |𝑧| ≤ 1, the recurrence gives 𝐹𝑖(2 √ 𝑟 𝑧) = 𝑟 𝑖/2𝑈𝑖(𝑧) − 𝑟 (𝑖−2)/2𝑈𝑖−2 (𝑧), where 𝑈𝑗 is the Chebyshev polynomial of the second kind. Using |𝑈𝑗(𝑧)| ≤ 𝑗 + 1 yields |𝜇(𝐹𝑖)| 𝐹𝑖(𝑘) ≤ 2𝑖 + 1 3 3 3−𝑖/2 .

p. 9
Where the paper says it

For |𝑧| ≤ 1, the recurrence gives 𝐹𝑖(2 √ 𝑟 𝑧) = 𝑟 𝑖/2𝑈𝑖(𝑧) − 𝑟 (𝑖−2)/2𝑈𝑖−2 (𝑧), where 𝑈𝑗 is the Chebyshev polynomial of the second kind. Using |𝑈𝑗(𝑧)| ≤ 𝑗 + 1 yields |𝜇(𝐹𝑖)| 𝐹𝑖(𝑘) ≤ 2𝑖 + 1 3 3 3−𝑖/2 .

In Proceedings of the 7th Python in Science Conference, pages 11–15, 2008

[23] Leonardo de Moura and Sebastian Ullrich. The Lean 4 theorem prover and programming language. p. 1

Where the paper says it

A diameter-four example, if one exists, has degree at least ten; see Theorems 4. • The standard one-variable nonbacktracking linear-programming hierarchy has exact ceiling 𝐵𝑘 = (𝑘 + 2) (𝑘 2 + 3) 6 , with a unique optimizer up to positive scaling; see Theorem 5.

p. 1
Where the paper says it

A diameter-four example, if one exists, has degree at least ten; see Theorems 4. • The standard one-variable nonbacktracking linear-programming hierarchy has exact ceiling 𝐵𝑘 = (𝑘 + 2) (𝑘 2 + 3) 6 , with a unique optimizer up to positive scaling; see Theorem 5.

In Automated Deduction—CADE 28, volume 12699 of Lecture Notes in Computer Science, pages 625–635. p. 1
Where the paper says it

The analytic arguments are proved in the text. Precisely specified finite classifications and matrix certificates are treated as computer-assisted proof components.

p. 1
Where the paper says it

The analytic arguments are proved in the text. Precisely specified finite classifications and matrix certificates are treated as computer-assisted proof components.

Springer, 2021

[24] The mathlib Community. The Lean mathematical library. p. 1

Where the paper says it

Our contribution is the specialization to the two-sided WOW window, the exact optimum for the admissible LP class of Section 5, the integral optimal-slack hierarchy, the edge-local cycle certificate, and the deletion theory developed below. We give an exact refutation of WOW-284 and a Lean 4.

p. 1
Where the paper says it

Our contribution is the specialization to the two-sided WOW window, the exact optimum for the admissible LP class of Section 5, the integral optimal-slack hierarchy, the edge-local cycle certificate, and the deletion theory developed below. We give an exact refutation of WOW-284 and a Lean 4.

In Proceedings of the 9th ACM SIGPLAN International Conference on Certified Programs and Proofs, pages 367–381, Association for Computing Machinery, 2020

Summary

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. This paper refutes WOW-284 with exact counterexamples for orders 38, 39, 40, 42, and 50 and develops a structural theory of the failure. p. 0

Where the paper says it

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.

Pruning redundant reasoning tokens

The authors prove that for a connected regular graph of girth at least five and diameter three, strict failure is equivalent to confining every nonprincipal adjacency eigenvalue to the open interval (−1 − √2k − 2, −1 + √2k − 2). They also prove that every regular strict counterexample has a degree of at least six and a diameter at most four. p. 0

Where the paper says it

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.

How the training signal is built

The spectral mechanism governing regular counterexamples is characterized by the formula Φ(G) = δ∗(G) + λmin(D(G)) > 0. For connected regular graphs of girth at least five and diameter three, this simplifies to Φ(G) = 2k − 2 − maxtheta≠k (θ + 1) squared. p. 1

Where the paper says it

Our main conclusions are as follows. • For connected regular graphs of girth at least five and diameter three, strict failure of WOW-284 is equivalent to confinement of every nonprincipal adjacency eigenvalue to the open interval (−1 − √ 2𝑘 − 2, −1 + √ 2𝑘 − 2); see Theorem 3.

This leads to the bound n ≤ B k = (k + 2) (k squared + 3) 6. p. 0
Where the paper says it

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 |𝑉 (𝐺) | ≤ 3(𝑘 + 2) 2 (𝑘 2 + 3) 18𝑘 + 41 ; this follows from a three-to-one quantization theorem for the integral excess.

Where the gains come from

The paper provides a detailed analysis of specific counterexamples, including Moore graphs and derived structures like the Anstee–Robertson graph and various subconstituent graphs. The stability analysis shows that every deletion of at most five vertices from the Hoffman–Singleton graph remains a strict counterexample, establishing a universal robustness radius of five. p. 1

Where the paper says it

• One-vertex, adjacent-pair, and nonadjacent-pair deletions of Moore graphs admit exact invariant-subspace decompositions for their recomputed distance matrices; see Section 7. • Every deletion of at most five vertices from the Hoffman–Singleton graph remains a strict counterexample, and this universal radius is sharp; see Theorem 8.

The authors determine the distance spectra for punctured Moore graphs and establish uniform deletion-stability bounds. For one deleted vertex from a degree-k Moore graph, the minimum dual degree is k − 1 / k, and the strictness holds exactly for integers k ≥ 5. p. 0

Where the paper says it

A degree-𝑘 Moore graph of diameter two has 𝐴 2 = (𝑘 − 1)𝐼 − 𝐴 + 𝐽, 𝐷 = 2𝐽 − 2𝐼 − 𝐴, and hence 𝛿 ∗ (𝐺) = 𝑘, 𝜆min (𝐷) = − 3 + √ 4𝑘 − 3 2 . The conjecture holds on these graphs exactly for 𝑘 ≤ 3, with equality at 𝑘 = 3, and fails for every realizable 𝑘 > 3.

The analysis of two nonadjacent deleted vertices yields an explicit distance characteristic polynomial that confirms strictness for every realizable integer k ≥ 6.

The analysis of the order-50 boundary reveals structural constraints on the signed complement matrix. The paper concludes that every connected 6-regular strict counterexample has an order at most 50. p. 0

Where the paper says it

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.

The final analysis of the degree-six boundary is highly constrained, although not yet eliminated. p. 0
Where the paper says it

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.

[1] Siemion Fajtlowicz. Written on the wall: Conjectures derived on the basis of the program Galatea Gabriella Graffiti. Technical report, University of Houston, 1998

[2] Mustapha Aouchiche and Pierre Hansen. Distance spectra of graphs: A survey. Linear Algebra and its Applications, 458:301–386, 2014

[3] Aditi Howlader and Pratima Panigrahi. On the distance spectrum of minimal cages and associated distance biregular graphs. Linear Algebra and its Applications, 636:115–133, 2022

[4] Miquel Àngel Fiol. Quotient-polynomial graphs. Linear Algebra and its Applications, 488:363–376, 2016

[5] Hiroshi Nozaki. Linear programming bounds for regular graphs. Graphs and Combinatorics, 31(6):1973–1984, 2015

[6] Sebastian M Cioabă, Jack H Koolen, Hiroshi Nozaki, and Jason R Vermette. Maximizing the order of a regular graph of given valency and second eigenvalue. SIAM Journal on Discrete Mathematics, 30(3):1509–1525, 2016

[7] Jörgen Backelin. Sizes of the extremal girth 5 graphs of orders from 40 to 49, 2015

[8] Paul R. Hafner. The Hoffman–Singleton graph and its automorphisms. Journal of Algebraic Combinatorics, 18(1):7–12, 2003

[9] M. O’Keefe and Pak-Ken Wong. A smallest graph of girth 5 and valency 6. Journal of Combinatorial Theory, Series B, 26(2):145–149, 1979

[10] Pak-Ken Wong. On the uniqueness of the smallest graph of girth 5 and valency 6. Journal of Graph Theory, 3(4):407–409, 1979

[12] Edwin R van Dam and Willem H Haemers. Which graphs are determined by their spectrum? Linear Algebra and its Applications, 373:241–272, 2003

[13] Markus Meringer. Fast generation of regular graphs and construction of cages. Journal of Graph Theory, 30(2):137–146, 1999

[14] Peter J Cameron, Jean-Marie Goethals, Johan J Seidel, and Ernest E Shult. Line graphs, root systems, and elliptic geometry. Journal of Algebra, 43(1):305–327, 1976

[15] Dragoš Cvetković, Peter Rowlinson, and Slobodan Simić. Spectral Generalizations of Line Graphs: On Graphs with Least Eigenvalue-2. Cambridge University Press, 2004

[16] Jack H Koolen, Kefan Yu, Xiaoye Liang, Harrison Choi, and Greg Markowsky. Non-geometric distance-regular graphs of diameter at least 3 with smallest eigenvalue at least -3. European Journal of Combinatorics, 126:104118, 2025

[17] Gary Greaves, Jack H Koolen, Akihiro Munemasa, Yoshio Sano, and Tetsuji Taniguchi. Edge-signed graphs with smallest eigenvalue greater than-2. Journal of Combinatorial Theory, Series B, 110:90–111, 2015

[20] Marién Abreu et al. A family of regular graphs of girth 5. Discrete Mathematics, 308(10):1810–1815, 2008

[21] Aaron Meurer et al. SymPy: Symbolic computing in Python. PeerJ Computer Science, 3:e103, 2017

[22] Aric A Hagberg, Daniel A Schult, and Pieter J Swart. Exploring network structure, dynamics, and function using NetworkX. In Proceedings of the 7th Python in Science Conference, pages 11–15, 2008

[23] Leonardo de Moura and Sebastian Ullrich. The Lean 4 theorem prover and programming language. In Automated Deduction—CADE 28, volume 12699 of Lecture Notes in Computer Science, pages 625–635. Springer, 2021

[24] The mathlib Community. The Lean mathematical library.

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Spectral inequality verification: The AI can perform exact computations for spectral certificates attached to explicit constructions of orders 38, 39, 40, and 42 using Lean 4.31 to certify dual-degree data and positive definiteness of relevant shifted distance matrices.

  2. LP ceiling optimization: The system can solve the one-variable nonbacktracking linear program exactly for admissible classes to determine the ceiling Bk = (k + 2) (k squared + 3) / 6, including optimizer rigidity.

  3. Integral slack matrix analysis: The AI can compute the integral excess r = 2(k + 2) squared (k squared + 3) - (12k + 27)n and verify the bound n <= (3(k + 2) squared (k 4 + 3)) / (18k + 41), including checking arithmetic rigidity for equality cases.

  4. Cycle count certification: The system can use the slack matrix's principal minors to recover local cycle constraints, specifically verifying the degree-six, order-50 contradiction where the signed complement is necessarily disconnected.

  5. Deletion stability analysis: The AI can apply invariant subspace decompositions to recomputed distance matrices for one-vertex, adjacent-pair, and nonadjacent-pair deletions of Moore graphs to establish uniform deletion stability bounds like every deletion of at most five vertices from the Hoffman–Singleton graph remains a strict counterexample.

  6. Exact graph realization verification: The system can check if specific parameters (k, n, r) correspond to an exact equality case by verifying that (18k + 41)r = Ck, which identifies the unique arithmetic parameter classification (k=103, n=185220).

  7. Local growth prediction: The AI can analyze normalized layer indicators and their characteristic polynomials to determine if a nonprincipal compression eigenvalue lies in the open WOW window theta + 1 < sqrt(2k - 2) or on the boundary, thus confirming whether a graph is a strict counterexample.

  8. Diameter and degree obstruction detection: The system can use the Rayleigh quotient bounds derived from distance-four pairs to confirm that no regular strict counterexamples exist for diameter four if the degree k is between 2 and 9.

  9. Exact enumeration of structural boundaries: For degree-six graphs, the system can utilize exact enumeration of triples (n0, n2, n4) satisfying m = n2 + 2n4 = 0 mod 5 to confirm that no graph of order at most 50 exists for which Φ(G) > 0.

  10. Signed-complement structural analysis: The AI can analyze the signed adjacency matrix T derived from Theorem 6.9 to prove that the edge-signed graph with adjacency matrix T is disconnected by showing its rank bound excludes known root systems like E8 for all possible connected support multigraphs.

Abstract

WOW-284 is a Graffiti conjecture asserting that every connected graph of order at least three and girth at least five has minimum dual degree at most-λ(D), where D is the distance matrix and the dual degree of a vertex is the average degree of its neighbors. We refute it with exact counterexamples on 38, 39, 40, 42 and 50 vertices and study the structure of regular counterexamples. For a connected k-regular graph G of girth at least five and diameter three, we prove that δ*(G)+λ(D)=2k-2- θ(θ+1) squared, the maximum being over the nonprincipal adjacency eigenvalues, so strict failure is a spectral window condition. The closed window θ+1 at most sqrt 2k-2 alone, without any diameter assumption, forces V(G)<(k+2)(k 2+3)/6 when k at least4, and an integral excess matrix derived from the optimal polynomial sharpens this bound for diameter-three counterexamples. Every regular strict counterexample has degree at least six and diameter at most four, and in degree six it has at most 50 vertices. Under vertex deletion, the Hoffman-Singleton graph remains a strict counterexample after the removal of any five vertices, while an explicit six-vertex deletion destroys strictness. A degree- 57 Moore graph, if one exists, remains a connected strict counterexample after the removal of any 56 vertices. Every strict counterexample has at least 15 vertices, and an exhaustive search excludes orders up to 19. The strict induced subgraphs of the Hoffman-Singleton graph of orders 36 to 50 are classified up to automorphism; among them are three further irregular counterexamples of order 40.

Sources

Related papers