Girth in Graph. A simple graph of girth 5 in which every vertex has degree at least $k$ has at least $k^{2}+1$ vertices, with equality achieveable when $k$ $\epsilon$ $\left \\{ 2,3 \right\\}$. Not getting how to solve !

Pick your starting vertex, _v_.

_v_ has at least _k_ neighbors (none of which are adjacent, because otherwise we have a cycle of length 3), call them $v_1, ... v_k$.

Each of the _k_ neighbors $v_i$ has at least $k-1$ neighbors besides $v$ itself. Call them $u_{i,1}, u_{i,k-1}$. The $u_{i,j}$ are distinct from all of the $v_i$, because otherwise we would have a cycle of length 3. Furthermore, all of the $u_{i,j}$ are distinct from each other, because otherwise we would have a cycle of length 4.

Count up the distinct vertices so far: There is 1 vertex $v$. There are $k$ vertices $v_i$. There are $k(k-1)$ vertices $u_{i,j}$.

$1 + k + k(k-1) = 1+k + k^2 -k = 1 + k^2$.

Equality is achievable when $k=2$ (just take a 5-cycle) or $k=3$ (the Petersen graph)