6
$\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?  

2 Answers 2

7

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.

  • 0
    +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"?2011-03-14
  • 0
    @Henry: I agree with the $g$ odd formula, but haven't checked the even one.2011-03-14
  • 0
    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.2011-03-14
  • 0
    Perhaps for even $g$ it is $2( (\delta-1)^{g/2}-1)/(\delta-2)$2011-03-14
  • 0
    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.2011-03-14
  • 0
    That is what I first thought. But sadly not - you will find some small cycles if you do that. Instead of one point, I think you need $(\delta-1)^{g/2-1}$ vertices opposite the starting point. Searching, I think my revised formula is now the same as that in [Wikipedia's article on Moore graphs](http://en.wikipedia.org/wiki/Moore_graph#Moore_graphs_as_cages)2011-03-14
  • 0
    @Henry: but we don't need regularity, which you do for a Moore graph. If $g=6$, you just need to avoid connecting any pair of new points to the same pair of old points. This looks like a place for an error-correcting code. We want a set of words of $\delta(\delta-1)^{g/2-2}$ bits, each bit on in $\delta-1$ words, with at most one bit overlap between any pair of words. The more bits we turn on in each word, the less words we need, and the words are the new vertices.2011-03-14
  • 0
    Of your $\delta(\delta-1)^{g/2-1}$ outward bound edges a couple of comments back, $(\delta-1)^{g/2-1}$ come from each of the $\delta$ branches(?) created at the start. Any point can only link up once to each branch without causing a short-circuit(?), so there must be a minimum of $(\delta-1)^{g/2-1}$ points in the final generation(?). (I don't know the correct jargon, but I hope the point is clear. Apparently this is a [cage](http://en.wikipedia.org/wiki/Cage_%28graph_theory%29).)2011-03-14
  • 0
    @Henry: I drew a sketch and you are right. And each point is satisfied because it gets $\delta$ of those incoming edges. So for even $g$ it is $(\delta (\delta-1)^{g/2-1}-2)/(\delta-2)+(\delta-1)^{g/2-1}=((2\delta-2) (\delta-1)^{g/2-1}-2)/(\delta-2)$ points2011-03-14
  • 0
    Just to be explicit for other readers, the right hand side of that expression simplifies to mine five comments back2011-03-14
0

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.