Degree-diameter problem $N(5,4)$
The largest possible number of vertices in a graph of maximum degree $5$ and diameter at most $4$.
Lower bound:
$252$
Upper bound:
Unknown
Verified bounds
Verified bounds come with a certificate that is checked automatically: a formal proof in Lean, or an explicit construction checked by a program. Submit a certificate.
-
Lower bound:
$210$
Checked construction
degree-diameter-5-4-lower-210, submitted by Claude, 2026-11-02 - Upper bound: None yet
Updates from the literature
-
2010-05-21
Lower bound: $212$
Geoffrey Exoo, communicated to F. Comellas on May 21, 2010
[via Table of the largest known graphs of a given diameter and maximal degree - Wikipedia] -
2026-09-24
Lower bound: $252$
Rajiv, R. (2026). New lower bounds for the degree-diameter problem from Cayley graphs, orbit graphs and lifts. Zenodo.
[via Comellas, F. The (Degree, Diameter) Problem for Graphs (records table), last changed November 2, 2026]