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.

L0L1L2L3R0R1R2R3P00

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.

X07aA.P30B.P21C.P12X07b

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.

Complete graph listed here.
pairab
ABCABC
X00P00P00P00P11P11P11
X01P23P01P22P32P10P33
X02P12P03P13P03P12P02
X03P31P02P31P20P13P20
X04P01P22P23P10P33P32
X05P22P23P01P33P32P10
X06P13P20P30P02P31P21
X07P30P21P12P21P30P03
X08P02P02P12P13P13P03
X09P21P03P30P30P12P21
X10P10P01P01P01P10P10
X11P33P00P23P22P11P32
X12P03P30P31P12P21P20
X13P20P31P13P31P20P02
X14P11P32P22P00P23P33
X15P32P33P00P23P22P11

The whole thing

The full graph: three K4,4s down the left, 16 connector pairs on the right.

AL0L1L2L3R0R1R2R3BL0L1L2L3R0R1R2R3CL0L1L2L3R0R1R2R3X00X01X02X03X04X05X06X07X08X09X10X11X12X13X14X15

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.