Prove $|V(G)| \ge k^2 + 1$ when all vertices in a graph $G$ have degree at least $k$ Suppose the shortest cycle in graph $G$ has length $5$. Prove that if every vertex of $G$ has degree at least $k$, then $G$ has at least $k^2+1$ vertices. 
So far, I have
$k \neq 0$, $k \neq 1$, or else we wouldn't have a cycle at all
If $k = 2$, then we would have a cycle (and by our question, it would be a $5$-cycle), and it would fit that $G$ has at least $k^2+1$ vertices ($2^2 + 1 = 5$).
My struggle is when $k \geq 3$. I know if I take any two vertices $u, v$, then each has $k-1$ neighbours other than each other, and that no neighbours of $u$ can be a neighbour of $v$ (else we'd have a smaller cycle of $3$). I'm not sure how to restrict it to be a size of $5$ though. Any advice?

Suppose we have a graph $G$ with shortest cycle with length at least $5$ and every vertex with degree at least $k$.
Pick a vertex $v_1$ in the graph. $v_1$ has degree at least $k$, so it is connected to $k$ other (distinct) vertices $v_2, v_3, \dots, v_{k+1}$. Now, each of these vertices is connected to at least $k$ other vertices and these vertices must all be distinct as well (as otherwise there would be a triangle in the graph). Therefore we have found at least $k^2 + 1$ distinct vertices in the graph.
