The girth of a graph is the length of the smallest polygon in the graph. Let G be graph with girth 5 for which all vertices have degree >=d. Show that G has at least d^2+1 vertices. Can equality hold? I am not sure, but how do I use the fact that the girth of G is 5, the only thing it tells me is that there are at least 5 vertices? Should I prove this statement by induction on d? What I did think of is using the fact the summing the degrees over all the vertices gives us that (1) 2|E|>=d*N, where N is the number of vertices and E is the set of edges of G. Now if I show that |E|>=(d^3+d)/2, and this is not a strict bound, then I prove it, but it seems even difficult than a proof by induction which I am not sure how to do also. Any hints?