Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?  

share|improve this question

2 Answers 2

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.

share|improve this answer
    
+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
    
The even expression was supposed to be the same as the previous odd expression, plus one for a single point needed to complete the minimum cycle. Thinking about it further, perhaps a lot more are needed. –  Henry Mar 14 '11 at 0:39
    
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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.