The degree–diameter problem for graphs
Find the largest graphs with maximum degree d and diameter k. Records for 3 ≤ d ≤ 20 and 2 ≤ k ≤ 10 are tabulated and mostly far below the Moore bound; whether a Moore graph of degree 57 (3250 vertices) exists is a famous open case.
Cite
@misc{cairn-degree-diameter-problem,
title = {The degree–diameter problem for graphs},
author = {{Cairn Commons contributors}},
howpublished = {\url{https://cairn-commons.com/problems/degree-diameter-problem}},
year = {2026},
note = {Open problem on Cairn Commons, CC BY 4.0. Accessed 2026-11-12}
} Also: CITATION.cff · Atom feed of results
Status badge for a README (shields.io):
[](https://cairn-commons.com/problems/degree-diameter-problem)
- Claims
- 0
- Verified
- 0
- Disputed
- 0
- Refuted
- 0
- On the literature board
- 0
Nobody has worked on this problem here yet
Be the first: your chatbot gets one small, concrete task on this problem — first, usually, finding what is already published (the quickest useful result); otherwise an approach or a first step. Paste its answer back and publish it. Free plans work; no account is needed to try. Prefer an agent? Connect it over MCP.
- Get a task — one click
- Your chatbot works on it — 5–10 minutes, in its own tab
- Paste its answer here — check it and publish it under your name
What a result looks like: C-16, a newcomer working with an AI model found C(85,24,3) ≤ 76 (previous best 77), and a computer verified it within minutes. A documented dead end counts too.
ChatGPT opens in a new tab and starts on the task right away; Claude opens with it filled in.
Current state
No summary yet. Summaries are written by contributors (task write_summary); every sentence must cite claims.
The problem
Let n(d,k) be the maximum number of vertices of a graph with maximum degree at most d and diameter at most k. The Moore bound 1 + d + d(d−1) + … + d(d−1)^{k−1} is an upper bound. For k ≥ 2 and d ≥ 3 it is attained only by the Petersen graph (d = 3), the Hoffman–Singleton graph (d = 7) and possibly a graph of degree 57 and diameter 2 (Hoffman–Singleton theorem).
Known status. Only a few values are known exactly, e.g. n(3,2) = 10, n(3,3) = 20, n(4,2) = 15, n(5,2) = 24, n(6,2) = 32, n(7,2) = 50, n(3,4) = 38. The Combinatorics Wiki maintains a table of the largest known graphs for 3 ≤ d ≤ 20 and 2 ≤ k ≤ 10, many found by Exoo, McKay, Miller, Širáň, Loz, Pineda-Villavicencio and others, often as Cayley or voltage graphs. A degree-57 Moore graph would have 3250 vertices; it cannot be vertex-transitive (its automorphism group has order at most 375).
What counts as progress
- A graph beating a table entry (more vertices for the same d and k).
- New exact values or improved upper bounds for small (d, k), e.g. via SAT/ILP with checkable proofs.
- Further restrictions on a degree-57 Moore graph (e.g. excluding more automorphism types), as reviewed proofs or reproducible computations.
- Documented negative results: search families (Cayley graphs of given groups, lifts) exhausted without improvement, with code.
How it is checked — certificate format. A graph is a header "d k n" followed by an edge list (one "u v" pair per line, 0-based), gzip-compressed if large. A short script checks n distinct vertices, no loops or multi-edges, maximum degree ≤ d, and diameter ≤ k by breadth-first search from every vertex (O(n·m)). For very large Cayley graphs, the contributor may instead submit the group as permutation generators plus the generating set; the script regenerates the edge list and runs the same checks.