Proving Vertex Count in a Graph with Girth 5 and Minimum Degree d

[MathematicalPhysicist]

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?

 

[mXSCNT]

Well, if the graph has girth 5, that means that if nodes A and B are adjacent, then B cannot be adjacent to any other node that A is adjacent to. Additionally, if B and C are both adjacent to A, then the intersection of the nodes adjacent to B and C is just A.

If a given node A connects to d other nodes, then there are (at least) d*(d-1) nodes other than A that are adjacent to nodes adjacent to A. And A can't connect to any of those. So for each node A in the graph, there are at least d*(d-1) nodes that are not adjacent to A. And there are at least d nodes that are adjacent to A. And then there's A itself. Adding all these nodes together, you get d*(d-1) + d + 1 = d^2 + 1.

 

[MathematicalPhysicist]

Thanks, I got to this same reasoning after someone else gave me a hint on how to solve this from another forum.