Q:

Graph with girth 5 and exactly $k^2+1$ vertices

I'm doing a homework and I've already done the proof that a graph with girth 5 and degree of atleast $k$ has at least $k^2+1$ vertices.
Also I've been able to found a graph for $k=2$ and $k=3$ but searching over the web I've found it's impossible to found one with $k=4$. How can I prove that it's impossible to find one?

A:

Two graphs that work are the Hoffman-Singleton graph (degree 7) and the Petersen graph (degree 3). 
For degree 4, you'd need a girth 5 graph with 17 vertices.  The fewest possible vertices is a cage graph, the Robertson graph, with 19 vertices. 

