The Moore bound is a bound obtained by counting the vertices in a tree-like neighborhood of a graph vertex before any vertex can be repeated. It occurs in two complementary extremal problems for graphs.
For the degree-diameter problem, a graph with maximum vertex
degree at most 
and graph diameter at most 
has at most
 |
(1)
|
vertices. This is the degree-diameter Moore upper bound. Equality gives a Moore graph in the degree-diameter sense.
For the cage graph problem, a 
-regular graph of girth 
has at least
 |
(2)
|
This is the degree-girth Moore lower bound. A cage graph attaining it is also called a Moore graph. The two forms use the same breadth-first counting idea, but one bounds order from above for specified degree and diameter while the other bounds it from below for specified degree and girth.
