Hoffman-Singleton Theorem

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).

The first three are the cycle graph  (), Petersen graph (), and Hoffman-Singleton graph (). The existence of the last is an unsolved problem.

REFERENCES

Bannai, E. and Ito, T. "On Moore Graphs." J. Fac. Sci. Univ. Tokyo Ser. A 20, 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. Algebra 1, 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.