The following problem is homework of a sort -- but homework I can't do!


The following problem is in Problem 1.F in *Van Lint and Wilson*: 



> 
> Let $G$ be a graph where every vertex
>  has degree $d$. Suppose that $G$ has
>  no loops, multiple edges, $3$-cycles
>  or $4$-cycles. Then $G$ has at least
>  $d^2+1$ vertices. When can equality
>  occur?
> 
> 
> 


I assigned the lower bound early on in my graph theory course. Solutions for $d=2$ and $d=3$ are easy to find. Then, last week, when I covered eigenvalue methods, I had people use them to show that there were no solutions for $d=4$, $5$, $6$, $8$, $9$ or $10$. (Problem 2 [here](http://www.math.lsa.umich.edu/~speyer/PSet6.pdf).) I can go beyond this and show that the only possible values are $d \in \{ 2,3,7,57 \}$, and I wrote this up in a [handout](http://www.math.lsa.umich.edu/~speyer/Solution6.pdf) for my students.


Does anyone know if the last two exist? I'd like to tell my class the complete story.



Is there a 7-regular graph on 50 vertices with girth 5? What about 57-regular on 3250 vertices?
This is the [Moore graph](http://en.wikipedia.org/wiki/Moore_graph), which is a regular graph of degree $d$ with diameter $k$, with maximum possible nodes. A calculation shows that the number of nodes $n$ is at most


$$
1+d \sum\_{i=0}^{k-1} (d-1)^i
$$


and as you mentioned it can be shown by spectral techniques that the only possible values for $d$ are


$$ d = 2,3,7,57. $$


Example for $d=7$ is the [Hoffman–Singleton graph](http://en.wikipedia.org/wiki/Hoffman-Singleton_graph), but for the case $d=57$ it is still open. See Theorem 8.1.5 in the book "[Spectra of graphs](http://homepages.cwi.nl/~aeb/math/ipm.pdf)" by Brouwer and Haemers for reference.


