# Let $G$ be a graph of girth $5$ for which all vertices have degree $\geq d$. Show that $G$ has at least $d^2+1$ vertices.

Could someone verify this?

Pick a vertex $v$ of $G$. Pick distinct vertices $u_1, u_2, \ldots, u_d$ incident with $v$. Note that this can be done since $v$ has no loops and degree $\geq d$. For each $u_i$, pick distinct vertices $w_i^{(1)}, w_i^{(2)}, \ldots, w_i^{(d-1)}$ incident with $u_i$ other than $v$.

Then, $$w_i^{(k)} \neq w_j^{(l)}$$ To see this, note that $v, u_i, w_i^{(k)}, u_j, v$ would form a cycle of length $4$. Also, $$w_i^{(j)} \neq u_k$$ To see this, note that $v, u_k, u_i, v$ would form a cycle of length 3.

Also, $$v \neq w_i^{(j)}$$

Otherwise, $v, u_i, v$ would form a cycle of length $2$.

So, all of the edges $v, u_1, \ldots, u_d, w_1^{(1)}, \ldots, w_d^{(d-1)}$ are distinct. So, the graph contains at least $1+d+d(d-1) = 1+d^2$ vertices.$~~~~~~~~~$

• You're right$~~$. – pointer Jun 15 '14 at 16:07

Let $V$ be the set containing the vertex $u$ and it's neighbors. We see that $|V|\geq d+1$ since every vertex in $G$ has degree at least $d$. None of $u$'s neighbors are adjacent since $G$ has girth $5$. Consider $V-u$, every vertex in $V-u$ has degree at least $d-1$ and $|V-u|=d$. So $|\bar{V}|\geq d(d-1)=d^2-d$. Thus $G$ has at least $(d+1)+(d^2-d)=d^2+1$ vertices.