Exercise 1692Combinatorics › Graph theoryM1Added 3 Nov 2026

Moore bound

#Moore bound#diameter#degree

Statement

State the Moore bound for a $d$ -regular graph of diameter $k$ .

Hint

BFS explores at most $d$ vertices at distance $1$ , $d(d-1)$ at distance $2$ , etc.

Show solutionHide solution

Bound. A $d$ -regular graph of diameter $k$ has at most
$1+d+d(d-1)+\cdots+d(d-1)^{k-1}$
vertices.

Equality. The Moore graphs (projective planes, etc.) attain this bound; they exist only for specific parameter values.

Conclusion. The Moore bound gives an upper bound on the order of $d$ -regular graphs of diameter $k$ .