The Hoffman-Singleton theorem restricts a regular graph of girth 5 and graph diameter
2 to degree 2, 3, 7, or 57. Let be a -regular graph with girth 5 and graph diameter 2. (Such a graph is a Moore
graph). Then, , 3, 7, or 57. A proof of this theorem is difficult (Hoffman
and Singleton 1960, Feit and Higman 1964, Damerell 1973, Bannai and Ito 1973), but
can be found in Biggs (1993).
Bannai, E. and Ito, T. "On Moore Graphs." J. Fac. Sci. Univ. Tokyo Ser. A20, 191-208, 1973.Biggs, N. L.
Ch. 23 in Algebraic
Graph Theory, 2nd ed. Cambridge, England: Cambridge University Press, 1993.Damerell,
R. M. "On Moore Graphs." Proc. Cambridge Philos. Soc.74,
227-236, 1973.Feit, W. and Higman, G. "The Non-Existence of Certain
Generalized Polygons." J. Algebra1, 114-131, 1964.Hoffman,
A. J. and Singleton, R. R. "On Moore Graphs of Diameter Two and Three."
IBM J. Res. Develop.4, 497-504, 1960.
be a 
-regular graph with girth 5 and graph diameter 2. (Such a graph is a Moore
graph). Then, 
, 3, 7, or 57. A proof of this theorem is difficult (Hoffman
and Singleton 1960, Feit and Higman 1964, Damerell 1973, Bannai and Ito 1973), but
can be found in Biggs (1993).
(
), Petersen graph (
),
and Hoffman-Singleton graph (
). The existence of the last is an unsolved
problem.
