Is there an infinite class of graphs with diameter 2, girth 5, and minimum degree at least 2?

Girth 5 is necessary, since otherwise complete bipartite graphs are an answer. Minimum degree at least 2 is necessary, since otherwise stars are an answer.

The Hoffman–Singleton graph (which has 60 vertices) is the largest graph I know with the properties in the question.

The question is interesting if "minimum degree at least 2" is replaced by "minimum degree at least 3", but I think it makes little difference because degree 2 vertices are highly restricted in a graph with diameter 2.

This question is related (but different) to the question Girth and diameter of a graph with minimum degree at least 3.


1 Answer 1


No infinite family exists. In fact all graphs with diameter $d$ and girth $2d+1$ have to be regular, and thus are Moore graphs. This was proved in

R. Singleton, "There is no irregular Moore graph", Amer. Math. Monthly 75 (1968), 42–43

See also the textbook "Algebraic Graph Theory" by Godsil and Royle (p. 90). It is unknown whether the Hoffman-Singleton graph is the largest Moore graph of girth 5 but if there are more, they have to be of degree 57 and of order 3250, thus there can only be finitely many more.

  • 1
    $\begingroup$ I don't think it's known that there is at most one Moore graph of degree $57$? $\endgroup$
    – verret
    Oct 4 at 5:06
  • 1
    $\begingroup$ @verret You are absolutely right. One hears the phrase "the missing Moore graph" so often, it is easy to forget there could be more than one. $\endgroup$ Oct 4 at 5:18
  • $\begingroup$ Thanks Gjergji. $\endgroup$
    – David Wood
    Oct 5 at 3:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.