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.(adsbygoogle = window.adsbygoogle || []).push({});

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?

**Physics Forums | Science Articles, Homework Help, Discussion**

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Girth of a Graph.

**Physics Forums | Science Articles, Homework Help, Discussion**