Degree diameter problem

Unsolved problem in mathematics

Given positive integers d and k, what is the maximum possible number of vertices in a finite simple graph of maximum degree at most d and diameter at most k?

More unsolved problems in mathematics

The Moore bound is attained by the complete graph $K_{d+1}$ when $k=1$ and by the odd cycle $C_{2k+1}$ when $d=2$.

In graph theory, the degree–diameter problem asks for the maximum possible number $n_{d,k}$ of vertices in a finite simple undirected graph of maximum degree at most $d$ and diameter at most $k$. A breadth-first search gives a general upper bound known as the Moore bound.

Exact equality in the Moore bound is exceptional. Apart from complete graphs, odd cycles, and the degree-one cases, the only known graphs attaining it are the Petersen graph and the Hoffman–Singleton graph; the only unresolved nontrivial parameter pair for equality is degree 57 and diameter 2. The exact value of $n_{d,k}$ is unknown for most pairs $(d,k)$.

A 2026 preprint by Wouter Cames van Batenburg and Samuel Korsky reports a proof that, for every fixed positive integer $k$,

$\lim _{d\to \infty }{\frac {n_{d,k}}{d^{k}}}=1.$

This resolves a conjecture of Béla Bollobás and shows that, for every fixed diameter, the Moore bound is asymptotically tight as the degree tends to infinity.

History and motivation

A principal motivation for the degree–diameter problem is the design of communication and computer interconnection networks. In this interpretation, vertices represent processors or other devices, maximum degree limits the number of direct connections available at a vertex, and diameter bounds the largest number of links that must be traversed between two vertices.

An early treatment connected with this application was given by Bernard Elspas in a 1964 paper on interconnection-limited logic.

Definition and Moore bound

For positive integers $d$ and $k$, define

$n_{d,k}=\max {\bigl \{}|V(G)|:\Delta (G)\leq d,\ \operatorname {diam} (G)\leq k{\bigr \}},$

where $\Delta (G)$ denotes the maximum degree of $G$. The elementary cases are

$n_{d,1}=d+1,\qquad n_{1,k}=2,\qquad n_{2,k}=2k+1.$

They are attained by complete graphs, a single edge, and odd cycles, respectively.

To obtain an upper bound, fix a vertex $v$. There are at most $d$ vertices at distance one from $v$, and at most $d(d-1)^{i-1}$ vertices at distance $i$, since each vertex other than $v$ has at most $d-1$ edges leading farther away from $v$. Consequently,

$n_{d,k}\leq M_{d,k}=1+d\sum _{i=0}^{k-1}(d-1)^{i},$

where $M_{d,k}$ is the Moore bound. Equivalently,

$M_{d,k}={\begin{cases}1+d\displaystyle {\frac {(d-1)^{k}-1}{d-2}},&d\geq 3,\\[6pt]2k+1,&d=2,\\2,&d=1.\end{cases}}$

For every fixed $k$,

$M_{d,k}=d^{k}+O_{k}(d^{k-1})$

as $d\to \infty$.

Moore graphs and defect

A graph attaining equality in the Moore bound is called a Moore graph. Any graph attaining the bound is necessarily regular.

Complete graphs $K_{d+1}$ are Moore graphs of diameter one, and the odd cycles $C_{2k+1}$ are Moore graphs of degree two. For diameter two and degree greater than two, Hoffman and Singleton showed that the only possible degrees are 3, 7, and 57. The Petersen graph and the Hoffman–Singleton graph realize degrees 3 and 7, respectively, while the existence of a Moore graph of degree 57 remains open. Damerell and, independently, Bannai and Ito proved that there are no Moore graphs other than cycles with diameter at least three.

For a graph $G$ of maximum degree at most $d$ and diameter at most $k$, the quantity

$\delta (G)=M_{d,k}-|V(G)|$

is called its defect. Moore graphs have defect zero. Graphs of small positive defect are studied as finite approximations to Moore graphs.

Bounds and constructions

Research on the degree–diameter problem proceeds in two complementary directions. Upper bounds and nonexistence results restrict the possible order of a graph, while explicit or probabilistic constructions provide lower bounds on $n_{d,k}$.

Construction methods have used finite geometries, Cayley graphs and other vertex-transitive graphs, graph lifts and voltage assignments, graph products and compounding, computational search, and probabilistic methods. For most nontrivial parameter pairs, the largest known construction has not been proved optimal.

Asymptotic behaviour

Two principal asymptotic regimes arise according to whether the degree or the diameter is held fixed.

Fixed degree

For $d=2$, the exact value is $n_{2,k}=2k+1$. For every fixed $d\geq 3$, Bollobás and Fernandez de la Vega showed that almost every $d$-regular graph on $n$ vertices has diameter

$(1+o(1))\log _{d-1}n$

as $n\to \infty$.

Together with the Moore bound, this gives

$n_{d,k}=(d-1)^{k+o(k)}$

as $k\to \infty$ for each fixed $d\geq 3$. Thus random regular graphs provide constructions with the optimal exponential growth rate. This result does not determine the asymptotic ratio $n_{d,k}/M_{d,k}$.

Fixed diameter

For fixed $k$, Delorme introduced the parameter

$\mu _{k}=\liminf _{d\to \infty }{\frac {n_{d,k}}{d^{k}}}.$

The 2013 survey by Miller and Širáň recorded that

$\mu _{1}=\mu _{2}=\mu _{3}=\mu _{5}=1$

and that

$\mu _{4}\geq {\frac {1}{4}}.$

For every fixed $k\geq 2$, Bollobás conjectured that

$\limsup _{d\to \infty }{\frac {n_{d,k}}{d^{k}}}=1.$

A stronger variant replaced the limit superior by the limit inferior. In their 2026 preprint, Wouter Cames van Batenburg and Samuel Korsky report a proof of the full limit

$\lim _{d\to \infty }{\frac {n_{d,k}}{d^{k}}}=1$

for every fixed positive integer $k$. Equivalently,

$\mu _{k}=1$

and

$\lim _{d\to \infty }{\frac {n_{d,k}}{M_{d,k}}}=1$

for every fixed $k$.

Their construction uses regular graphs whose vertices are partial flags in vector spaces over finite fields. The preprint is accompanied by a Lean 4 formalization of its central theorem chain, including the asymptotic theorem.

Relation to the degree–girth problem

The related degree–girth problem asks for the smallest possible order of a regular graph with prescribed degree and girth. For a $d$-regular graph of odd girth $2k+1$, breadth-first counting gives $M_{d,k}$ as a lower bound on its order. A graph attaining this lower bound is simultaneously a cage and a Moore graph.

For even girth, an analogous count leads to the bipartite Moore bound and the study of bipartite Moore graphs.

Directed and restricted variants

For a directed graph of maximum out-degree at most $d$ and directed diameter at most $k$, the directed Moore bound is

$M_{d,k}^{\rightarrow }=1+d+d^{2}+\cdots +d^{k}={\begin{cases}\displaystyle {\frac {d^{k+1}-1}{d-1}},&d>1,\\[6pt]k+1,&d=1.\end{cases}}$

A digraph attaining the bound is called a Moore digraph. Moore digraphs exist only in the elementary cases $d=1$, represented by directed cycles, and $k=1$, represented by complete digraphs.

Restricted forms of the degree–diameter problem have been studied for Cayley graphs, vertex-transitive graphs, bipartite graphs, planar graphs, graphs embeddable on a fixed surface, and several other graph classes.

Known values and open problems

Exact values of $n_{d,k}$ are known for relatively few nontrivial parameter pairs. For most pairs, only upper bounds and the orders of the largest currently known constructions are available; these are recorded in the Table of the largest known graphs of a given diameter and maximal degree.

The existence of a Moore graph of degree 57 and diameter 2 remains open. Other questions concern the optimal rate at which $n_{d,k}/d^{k}$ tends to one for fixed $k$, and the regime in which both degree and diameter tend to infinity. In particular, it is unknown whether

${\frac {n_{d,k}}{M_{d,k}}}\longrightarrow 1$

along every sequence for which both $d$ and $k$ tend to infinity, and whether the Moore gap

$M_{d,k}-n_{d,k}$

is unbounded.

See also

• Cage (graph theory)
• Table of the largest known graphs of a given diameter and maximal degree
• Table of vertex-symmetric degree–diameter digraphs
• Maximum degree-and-diameter-bounded subgraph problem