7
$\begingroup$

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?  

$\endgroup$

2 Answers 2

9
$\begingroup$

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.

$\endgroup$
10
  • $\begingroup$ +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"? $\endgroup$
    – Henry
    Mar 14, 2011 at 0:14
  • $\begingroup$ @Henry: I agree with the $g$ odd formula, but haven't checked the even one. $\endgroup$ Mar 14, 2011 at 0:33
  • $\begingroup$ 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. $\endgroup$
    – Henry
    Mar 14, 2011 at 0:39
  • $\begingroup$ Perhaps for even $g$ it is $2( (\delta-1)^{g/2}-1)/(\delta-2)$ $\endgroup$
    – Henry
    Mar 14, 2011 at 0:55
  • $\begingroup$ 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. $\endgroup$ Mar 14, 2011 at 0:59
0
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.