For fixed integers $latex r > 0$, and odd $latex g$, a *Moore graph* is an $latex r$-regular graph of girth $latex g$ which has the minimum number of vertices $latex n$ among all such graphs with the same regularity and girth.

(Recall, A the girth of a graph is the length of its shortest cycle, and it’s regular if all its vertices have the same degree)

**Problem (Hoffman-Singleton): **Find a useful constraint on the relationship between $latex n$ and $latex r$ for Moore graphs of girth $latex 5$ and degree $latex r$.

*Note: *Excluding trivial Moore graphs with girth $latex g=3$ and degree $latex r=2$, there are only two known Moore graphs: (a) the Petersen graph and (b) this crazy graph:

The solution to the problem shows that there are only a few cases left to check.

**Solution: **It is easy to show that the minimum number of vertices of a…

View original post 761 more words