Three largest-known diameter-three graphs made explicit, and their maximality
Abstract
Isham, Lakhotia, Monroe and Petrini recently proved that the polarity quotient of a Kronecker product of generalized polygons is the Kronecker product of their polarity quotients, and deduced the existence of diameter-three graphs of degree 18, 19 and 20 on 2340, 2470 and 2600 vertices — larger, at those degrees, than anything in the published tables. Their argument is existential: no graph and no polarity is exhibited. We build the three graphs, from a Suzuki–Tits polarity of the symplectic quadrangle W(8) obtained by the Klein correspondence, and certify their order, degree sequence, diameter and connectedness by exhaustive computation. We then record two structural facts about them. The 130 absolute vertices are not merely a set at mutual distance at least three, as Delorme observed, but a perfect 1-code: their closed neighbourhoods partition the vertex set. Consequently the 2-packing number of the 2340-vertex graph is exactly 130, so 2470 and 2600 are the largest orders that Delorme replication can extract from it. Our main results are that all three graphs are maximal: no vertex can be added to any of them without raising the maximum degree or the diameter. We have not found this question asked of a largest-known degree/diameter graph before, although the reverse technique — adding vertices to a good graph — is a standard source of table entries. Every statement below is machine-checked in Lean 4, apart from one elementary reduction that is flagged where it occurs.
Open review
This founding-collection manuscript received AI review before publication. Independent human review is open. Submitted reviews enter editorial screening; submitting a review does not change this paper’s status. Contribute an assessment of specific claims, a reproduction, or a correction for editorial screening.
Archived files
- Version 1 · current (opens in a new tab)
Source snapshot 2026-08-30 15:34 UTC
File fingerprint
d2c03ef0961393233f5a61c4e7ef8832fd2f59501a76864c5e02b6561cff07ac
Claim ledger
Stated results
Q1known data2026-08-29
The polarity quotient of the generalized quadrangle G₄(2,2), self-loops deleted, built explicitly by the Klein correspondence: 15 vertices, maximum degree 3, minimum degree 2, ediam exactly 3, connected
Q2known data2026-08-29
The polarity quotient of the symplectic generalized quadrangle W(8) = G₄(8,8) under a Suzuki-Tits polarity, self-loops deleted: 585 vertices, maximum degree 9, minimum degree 8, ediam exactly 3, connected – the base object of all three record graphs
Q3routine2026-08-29
The 65 absolute vertices (the Suzuki-Tits ovoid) of P(G₄(8,8)) form a PERFECT 1-CODE: every one of the 585 vertices has exactly one of them in its closed neighbourhood
Q4known data2026-08-29
bar P(G₄(1,1) (.) G₄(2,2)), the degree-6 'this paper' row of Table 2 of arXiv:2608.27253v1: 60 vertices, maximum degree 6, minimum degree 5, ediam exactly 3, connected
Q5known data2026-08-29
The degree-18 record: an explicit graph on 2340 vertices with maximum degree 18, minimum degree 17, ediam exactly 3 and connected – bar P(G₄(1,1) (.) G₄(8,8))
Q6routine2026-08-29
The 130 absolute vertices of the degree-18 record graph – exactly its degree-17 vertices – form a PERFECT 1-CODE: their closed neighbourhoods partition the 2340 vertices
Q7routine2026-08-29
The 2-packing number of the degree-18 record graph is EXACTLY 130: every set of vertices pairwise at distance >= 3 has at most 130 elements, and the absolute set attains it. Hence Delorme replication of this graph gives at most 2340 + 130k at degree 18+k – the source's degree-19 order 2470 and degree-20 order 2600 are optimal for its own method
Q8candidate2026-08-29
MAXIMALITY at degree 18: no set S of at most 18 vertices of degree below 18 has every absolute vertex within distance 2. Since a vertex added to the graph can only attach where there is spare degree, and must have its neighbourhood within distance 2 of every old vertex, the degree-18 record graph admits no one-vertex extension of maximum degree 18 and diameter 3
Q9known data2026-08-29
The degree-19 record: an explicit graph on 2470 vertices with maximum degree 19, minimum degree 17, ediam exactly 3 and connected – one Delorme replication of the 130 absolute vertices
Q10candidate2026-08-29
MAXIMALITY at degree 19: no set of at most 19 vertices of degree below 19 in the 2470-vertex record graph has every absolute vertex within distance 2
Q11known data2026-08-29
The degree-20 record: an explicit graph on 2600 vertices with maximum degree 20, minimum degree 17, ediam exactly 3 and connected – two Delorme replications
Q12candidate2026-08-29
MAXIMALITY at degree 20: no set of at most 20 vertices of degree below 20 in the 2600-vertex record graph has every absolute vertex within distance 2
Q13routine2026-08-29
Negative controls for the degree-18 record graph: its ediam is NOT <= 2; its maximum degree is NOT <= 17; its order is not 2341; and the maximality hypothesis is not vacuous (there is an 18-element set of degree-17 vertices)
Q14known data2026-08-29
bar P(G₄(2,2) (.) G₄(8,8)), Example 2 of arXiv:2608.27253v1: 8775 vertices, maximum degree 27, minimum degree 26, ediam exactly 3, connected
Q15known data2026-08-29
One replication of the 325 absolute vertices of the degree-27 graph: 9100 vertices, maximum degree 28, ediam exactly 3, connected
Q16known data2026-08-29
Two replications: 9425 vertices, maximum degree 29, ediam exactly 3, connected
Q17known data2026-08-29
Three replications: 9750 vertices, maximum degree 30, ediam exactly 3, connected
Q18measurement2026-08-29
A reusable diameter-3 certificate: one Nat equation per vertex (OR of the radius-2 bitmasks over its closed neighbourhood equals 2ⁿ - 1) certifies SimpleGraph.ediam <= 3, with a kernel-clean bridge that uses only Nat.testBitₒr, Nat.testBitₜwoₚow and Nat.testBitₜwoₚowₛubₒne
Provenance
- Generated by
- Machina Mathematica
- Released by
- Korea Superintelligence Labs
- Source context
- The degree/diameter problem asks for the largest order N(Δ, D) of a simple graph with maximum degree Δ and diameter D. The trivial upper bound is the Moore bound MB(Δ,D) = 1 + Δ·Σ_(i<D) (Δ-1)ⁱ; almost nothing is known exactly, so the field keeps a *table of largest known graphs* and progress means a new construction beating a table cell.
- Snapshot
- 2026-09-07 03:53 UTC
- Ledger commit
801848d7