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.
