The largest known degree-4, diameter-4 graph

104 vertices and 208 edges, with every vertex at degree 4 and any two at most 4 steps apart, built from three identical blocks and a set of connectors between them.

The building block is a subdivided K_4,4: a complete bipartite graph between four “L” and four “R” vertices, each of its 16 edges split by a vertex in the middle. The vertex splitting Li–Rj is port Pij. That is 4 + 4 + 16 = 24 vertices and 32 edges per block.

Three copies — A, B and C — account for 72 vertices and 96 edges. An Li or Rj is already at degree 4; a port is at 2, short two edges.

The remaining 32 vertices are connectors, in 16 matched pairs: X01a/X01b through X16a/X16b. Each runs one edge to its partner and one into each block, so it too sits at degree 4, and each port takes two of those, which brings the ports up as well. That is 16 matching edges and 96 connector–port edges, for 104 vertices and 208 in total.

The one thing none of that determines is which port in each block a given connector reaches. It is the construction's free parameter, and it is what the diameter turns on. The assignment used here is below.

Complete graph listed here.

pair	a			b
	A	B	C	A	B	C
X01	P11	P11	P11	P22	P22	P24
X02	P34	P12	P32	P43	P21	P43
X03	P23	P14	P23	P14	P23	P12
X04	P42	P13	P44	P31	P24	P31
X05	P12	P33	P33	P21	P44	P42
X06	P33	P34	P14	P44	P43	P21
X07	P24	P31	P41	P13	P42	P34
X08	P41	P32	P22	P32	P41	P13
X09	P13	P13	P22	P24	P24	P13
X10	P32	P14	P41	P41	P23	P34
X11	P21	P12	P14	P12	P21	P21
X12	P44	P11	P33	P33	P22	P42
X13	P14	P41	P44	P23	P32	P31
X14	P31	P42	P23	P42	P31	P12
X15	P22	P43	P32	P11	P34	P43
X16	P43	P44	P11	P34	P33	P24

The whole thing

Laid out as a board: the three blocks along the top, each with its L branches on its top edge and its R branches down its left; the channel underneath carrying all 96 connector–port cables; the 32 connectors in a single row; and the matching below them as sixteen staples, each joining the two connectors of one pair.