# If given the girth and the minimum degree of a simple graph $G$, can we give a lower bound on the number of vertices it has?

I'm trying to prove that every simple graph $G$ of girth $g(G)=5$ (length of smallest cycle), and minimum degree $\delta$, has at least $\delta^2 + 1$ vertices. I tried using induction on $\delta$ without any results, and also tried to apply the pigeonhole principle, to no avail.

Help?

-

If you start from any vertex, it is connected to at least $\delta$ vertices. Each of those is connected to at least $\delta-1$ others. These are all distinct or you would have a 4 (or less)-cycle. $1+\delta+\delta(\delta-1)=\delta^2+1$. The pentagon and Petersen graph follow exactly this, then connect appropriate ones of the second tier of vertices.
+1 Very neat. So can we say something like "with smallest cycle length $g$ and minimum degree $\delta$, there are at least $(\delta (\delta-1)^{(g-1)/2}-2)/(\delta-2)$ vertices if $g$ is odd, and $(\delta (\delta-1)^{g/2-1}+\delta-4)/(\delta-2)$ vertices if $g$ is even"? – Henry Mar 14 '11 at 0:14
@Henry: I agree with the $g$ odd formula, but haven't checked the even one. – Ross Millikan Mar 14 '11 at 0:33
Perhaps for even $g$ it is $2( (\delta-1)^{g/2}-1)/(\delta-2)$ – Henry Mar 14 '11 at 0:55
For the even case, you have $\delta(\delta-1)^{g/2-2}$ vertices in the outer complete ring, each of which only has one inward connection. So we have $\delta(\delta-1)^{g/2-1}$ outward bound edges. But they could all go to one point if you want. So I think your first even case is correct, too. – Ross Millikan Mar 14 '11 at 0:59
Suppose for a simple graph $G$, $g(G) = 5$ and $\delta(G)$ is the minimum degree. Suppose for contradiction that $G$ has $\delta^2$ vertices. You can probably use Menger's Theorem to come up with a contradiction.