August 22nd, 2026
Largest known degree-4, diameter-4 graph
104 vertices and 208 edges. As of August 22nd, 2026, this is the largest known degree-4, diameter-4 graph. In simple terms, every vertex has 4 neighbors (degree-4), and no two vertices are more than 4 apart (diameter-4).
Building blocks
The graph is built from three K4,4 graphs: complete bipartite graphs between four "L" and four "R" vertices. Each Li and Rj is connected via a port Pij, for 24 vertices and 32 edges per K4,4.
The three of these account for 72 vertices and 96 edges. Every Li and Rj is already at degree 4; every port is at degree 2, short two edges.
Connecting the blocks
The remaining 32 vertices are connectors between the K4,4s, in 16 matched pairs: X00a/X00b through X15a/X15b. Each connector has one edge to its partner and one edge into each K4,4, bringing it to degree 4 and filling the 2 missing edges on each port.
Port assignment
This still leaves out the one thing that makes the graph work: the exact mapping between connectors and ports. That's the construction's free parameter, and it's what gets the diameter down to 4. One such assignment is shown below.
| pair | a | b | ||||
|---|---|---|---|---|---|---|
| A | B | C | A | B | C | |
| X00 | P00 | P00 | P00 | P11 | P11 | P11 |
| X01 | P23 | P01 | P22 | P32 | P10 | P33 |
| X02 | P12 | P03 | P13 | P03 | P12 | P02 |
| X03 | P31 | P02 | P31 | P20 | P13 | P20 |
| X04 | P01 | P22 | P23 | P10 | P33 | P32 |
| X05 | P22 | P23 | P01 | P33 | P32 | P10 |
| X06 | P13 | P20 | P30 | P02 | P31 | P21 |
| X07 | P30 | P21 | P12 | P21 | P30 | P03 |
| X08 | P02 | P02 | P12 | P13 | P13 | P03 |
| X09 | P21 | P03 | P30 | P30 | P12 | P21 |
| X10 | P10 | P01 | P01 | P01 | P10 | P10 |
| X11 | P33 | P00 | P23 | P22 | P11 | P32 |
| X12 | P03 | P30 | P31 | P12 | P21 | P20 |
| X13 | P20 | P31 | P13 | P31 | P20 | P02 |
| X14 | P11 | P32 | P22 | P00 | P23 | P33 |
| X15 | P32 | P33 | P00 | P23 | P22 | P11 |
The whole thing
The full graph: three K4,4s down the left, 16 connector pairs on the right.
I originally found an asymmetric variant of this graph via a Z8 voltage graph lift of a 13-vertex base multigraph. After much effort yet failing to push past n=104, I revisited the graph and noticed it could be simplified into the more structured form shown here. I'm 40% confident it's optimal, but time will tell. :)
Given the progress I made here with the assistance of Claude Fable, I decided to let it loose on the rest of the degree-diameter table, with good success.