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
    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.