MathRSI · Research Case

Degree–Diameter

Record improvements with dated public benchmarks

Two new improvements to the Comellas record table. Our results reported on 16 November 2026 reach 37,632 vertices at (11,5) and 42,433 at (12,5), exceeding the listed records by 1 and 81 vertices. A fresh check on 18 November 2026 confirms the same gains. Earlier record improvements, including 2,567 vertices at (10,4) and 16,416 at (16,4), retain their original comparison dates.

Latest bilingual result and methods · 中文版 · Illustrated case and record timeline

Record timeline

(Δ,D)Our constructionPublic-table baselineGain and comparison date
(10,4)2,5672,566+1 · 5 November 2026
(11,5)37,63237,631+1 · 16 November 2026; rechecked 18 November
(12,5)42,43342,352+81 · 16 November 2026; rechecked 18 November
(16,4)16,41616,384+32 · 5 November 2026

Each row records an improvement over the public table at the stated time. Later advances extend this record history; they do not change what an earlier construction achieved when reported. Comparison dates and sources.

Latest D5 improvements · reported 16 November 2026

Public table last checked: 18 November 2026.

(Δ,D)Previous local graphLatest graphLocal increaseComellas 2026-11-18Gain over that table
(11,5)37,63137,632+137,631+1
(12,5)42,40242,433+3142,352+81

The final graphs have 205,366 and 246,309 edges, maximum degree 11 and 12, and diameter exactly five, respectively. The 31 D12 insertions improve our previous 42,402-vertex construction by 31 vertices; the gain over the dated public-table entry is 81.

Run provenance: local 2026-11-11 main/v4-maintenance plus DD feedback. The research predates the published v5 workflow and feeds v5 main maintenance, while the fixed v5 tag remains unchanged. On the timeline this is shortened to “Run: v4 + local updates”.

Method and actual checks. D12 preserves the full source as an induced subgraph and adds 31 vertices through legal available-degree attachments. All 31 new vertices were BFS roots in the final graph; old–old distances inherit the accepted source premise. D11 changes the core, so source-edge retention is insufficient: its core distances use the H9 geometric theorem and literal binding, while all 160 old peripheral vertices and the new vertex supply 161 complete BFS roots. Both finals were regenerated exactly; independent finite-array/degree checks passed. Concrete end-to-end Lean instances and required source final-review obligations remain open.

The Comellas table advances as new constructions arrive. On 18 November 2026, it lists 2,614 for (10,4) and 16,848 for (16,4). Our 2,567- and 16,416-vertex graphs remain documented as improvements over the records checked on 5 November 2026. The two D5 graphs above still exceed the table in this latest check.

Joint completion and verified prefixes. Use an inclusion-minimal core-blocking set and jointly complete attachments from the full pool of remaining degree ports. Actual bad vertex pairs guide revisions to earlier construction choices; subsequent work consumes only independently verified prefixes. This research also feeds the Base action Consume results before dispatch: Update current facts from returned evidence before issuing the next task or review, preventing duplicate work and stale-state rollback. v5 follow-up record.

Private source package and replay · v5 maintenance notes

Historical research and illustrated methods

The degree–diameter problem asks how many vertices a simple undirected graph can have when each vertex has at most Δ neighbors and every pair of vertices is connected by a path of length at most D. Earlier ARIS research developed neighborhood extensions, finite-field layers and geometric connection reallocation. The earlier (10,4) result was obtained using MathRSI v2 and its degree–diameter plugin, continuing that research with its saved constructions and failure trajectories. Execution version.

Read the illustrated case · 中文版 · Construction programs

Clone or download the repository and open index.html locally for the interactive figures. GitHub displays the HTML source; this README is the overview to read on GitHub.

Historical November 2026 table comparisons and published-method comparisons for diameter three

Earlier record improvements · 5 November 2026

The following constructions improved four entries in the Comellas table, checked on 5 November 2026. That snapshot includes a 10-regular graph of diameter 4 on 2,567 vertices, exceeding the table's 2,566 vertices.

(Δ,D)Comellas tableOur constructionAdditional vertices
(10,4)2,5662,567+1
(11,5)37,62837,631+3
(12,5)42,34242,402+60
(16,4)16,38416,416+32

The diameter-three constructions cover seven consecutive degrees, from 20 to 26. Their comparisons use the specified published constructions and formulas, including Rajiv, PolarStar, and Delorme's methods. These method-based benchmarks are identified separately from the dated Comellas table records above.

Δ, with D = 3Published-method referenceOur constructionAdditional vertices
202,7913,840+1,049
212,9283,984+1,056
223,2944,192+898
233,5494,336+787
246,1446,160+16
257,2257,242+17
267,5147,532+18

Across 37 diameter-three parameter pairs, our constructions exceed these specified public-method references. Examples at higher degrees include 56,862 vertices for (54,3), an increase of 1,350, and 414,132 vertices for (98,3). Sources and comparison formulas give the 1 November 2026 literature review and the scope of each comparison.

How the constructions work

1. Extend a graph through covering neighborhoods

Keep the original edges and connect a new vertex x to a set S of existing vertices. If the radius-(D−1) neighborhoods around S cover the current graph, every vertex is within D steps of x. Each selected neighbor must also have room for the new edge. Repeating this argument gives the D5 extension sequences; neighborhood cloning supports related D3 and D4 constructions.

Connecting x only to vertex 0 leaves vertex 7 at distance 4. The degree bound holds, but the diameter bound fails.
Connecting x only to vertex 0 leaves vertex 7 at distance 4. The degree bound holds, but the diameter bound fails.
A cube example showing how complementary neighborhoods allow an additional vertex while respecting degree and diameter limits
Connecting x to opposite corners 0 and 7 covers all eight original vertices within three steps, with degrees at most 4.
A second vertex y attached to 0 and 7 preserves coverage, but raises both attachment points to degree 5, exceeding the limit of 4.
A second vertex y attached to 0 and 7 preserves coverage, but raises both attachment points to degree 5, exceeding the limit of 4.
Attaching y to 1 and 6 covers all nine existing vertices, including x, while keeping every degree at most 4.
Attaching y to 1 and 6 covers all nine existing vertices, including x, while keeping every degree at most 4.

Connecting x to opposite corners 0 and 7 covers all eight original vertices within three steps, with degrees at most 4.

The interactive illustration compares four choices on a cube: one attachment misses a vertex; complementary attachments cover it; reusing the same attachment points exceeds their degree limit; choosing different points allows another extension.

The earlier (10,4) construction extends this idea to a graph with no unused degree capacity. Starting from 2,566 vertices, we remove five disjoint edges and connect a new vertex to all ten endpoints. Every affected old vertex returns to degree 10, and the new vertex has degree 10. Failed point pairs guided the subsequent choices of edges; the final 2,567-vertex graph passes the complete distance check.

Five disjoint edges are replaced by ten connections to a new vertex, increasing the order from 2,566 to 2,567 while keeping degree 10

Exact recipe, construction program and verification accompany the ten accepted intermediate versions from 2,558 to 2,567 vertices.

2. Lift a small controller over a finite field

The 3,840-vertex, degree-20 graph uses 60 controller states, each carrying the 64 points of F₄³. Five controller ports supply four neighbors each. Compatible affine maps make three-step routes cover the required coordinate layers. Moving from shared parameters to edge-specific maps resolved the compatibility obstacle in the F4 construction.

A 60-state controller with 64-point fibers produces 3,840 vertices and 20 neighbors per vertex

3. Reallocate geometric connections

Spreads and ovoids in generalized quadrangles organize compatible filling and cloning positions. In the 7,531 → 7,532 construction, 17 clone–filler edges are replaced by 17 edges from a new hub to the fillers. Alternative short routes preserve the distance bound, while the edge count remains 97,750.

Replacing 17 clone–filler connections with 17 hub–filler connections adds a vertex without increasing the edge count

The construction builds on source graphs and controllers by Mizuno, Rajiv, Yugeswardeenoo, and Bhakar/f4t4nt, together with Delorme's and subsequent finite-geometry methods. Construction notes connect the illustrations to the underlying arguments and source programs.

What carries over to new problems

The successful steps changed how connections were chosen: combine neighborhoods that cover different regions, allocate degree capacity across all additions, and replace a connection only when the affected routes can be recovered. These lessons turn an individual construction into a starting point for a family of parameters. The proofs, counterexamples and construction programs informed MathRSI's degree–diameter plugin, which connects these methods to the research workflows in v2.

Historical verification and reproduction

The 5 November 2026 catalogue snapshot contains 163 graphs with mathematical or computational verification; 49 have proofs of their concrete graph constructions in Lean, including the 2,567-vertex graph and all seven degree-20–26 representatives. The catalogue includes intermediate extensions, with each parameter comparison using its largest construction.

The HTML is generated from this README with ARIS /render-html. Edit the Markdown and run python3 tools/render_index.py from the case directory to update the English and Chinese readers.

MathRSI · GitHub ↗