A Moore graph, named after E. F. Moore, of type 
is a regular graph of
vertex degree 
and girth 
that contains the minimum possible number of nodes, namely
the Moore bound
 |
(1)
|
(Bannai and Ito 1973; Royle).
Equivalently, it is a 
-cage graph, where 
is the vertex degree and
is the girth,
with an excess of zero (Wong 1982). Moore graphs are also
called minimal 
-graphs
(Wong 1982), and are always distance-regular.
The numbers of Moore graphs on 
, 2, ... nodes are 0, 0, 0, 1, 1, 2, 1, 2, 1, 3, 1, 2, 1,
.... The following table lists some Moore graphs (excluding complete
graphs and complete bipartite graphs).
 | named Moore graphs (or reference) |
 | Petersen graph  |
 | Heawood graph |
 | Tutte 8-cage |
 |  -cage (Wong 1982) |
 | order-4 generalized triangle |
 | Hoffman-Singleton graph |
Hoffman and Singleton (1960) introduced the term "Moore graph" because E. F. Moore had posed the problem of describing graphs attaining equality
in the degree-diameter bound. They showed that there is a unique Moore graph for
types 
(Petersen graph) and 
(Hoffman-Singleton
graph), where 
is the graph diameter, but no other 
Moore graphs with the possible exception of 
(Bannai and Ito 1973). For the degree-diameter definition,
Damerell (1973) and Bannai and Ito (1973) showed that there are no Moore graphs of
graph diameter 
and valence 
. In the girth-based definition used here, after excluding
complete graphs (
) and complete bipartite
graphs (
),
a 
-Moore graph can exist only if (1)
and 
, 7, or (possibly) 57, or (2) 
, 8, or 12 (Feit and Higman 1964; Wong 1982). These are necessary
parameter restrictions, not a complete existence and uniqueness classification of
the even-girth graphs. The possible degree-57, diameter-2 Moore graph remains open.
The degree-diameter classification is discussed in Biggs (1993); its diameter-2 case
is the Hoffman-Singleton theorem.
Makhnev (2020) claimed a proof that a Moore graph of vertex degree 57 and graph diameter 2 does not exist, but Faber and Keegan (2023, pp. 31-32) subsequently identified a gap in this argument. The necessary linear systems of equations used in the proof admit nonnegative integer solutions, so the claimed contradiction does not follow.
Moore graphs should not be confused with the Moore four-color graph, a 341-vertex planar graph used as a test case for graph four-coloring.
