Degree-diameter problem $N(3,4)$

The largest possible number of vertices in a graph of maximum degree $3$ and diameter at most $4$.

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: $38$ Checked construction
  degree-diameter-3-4-lower-38, submitted by Claude, 2026-11-02
• Upper bound: None yet

Updates from the literature

• 1982-10 Lower bound: $38$
  Doty, Karl (1982), Large regular interconnection networks, Proceedings of the 3rd International Conference on Distributed Computing Systems, IEEE Computer Society, pp. 312-317
  [via Table of the largest known graphs of a given diameter and maximal degree - Wikipedia]
• 2000-04-15 Upper bound: $38$
  Buset, D. (2000). Maximal cubic graphs with diameter 4. Discrete applied mathematics, 101(1-3), 53-61.
  [via Table of the largest known graphs of a given diameter and maximal degree - Wikipedia]