Induction generally works pretty badly on regular graphs (graphs in which every vertex has the same degree). Induction on graphs is all about the idea that to deal with an $m$-vertex graph, you delete a vertex and apply the inductive hypothesis to the $(m-1)$-vertex graph. But in this case, if you delete a vertex from a regular graph, the remainder is no longer regular, so the inductive hypothesis does not apply.
If you stick with the idea of induction, you want to generalize the claim. We can try to prove that in any graph which has no length-$3$ cycles, and in which every vertex has at least $n$ neighbors, there must be at least $2n$ vertices total.
If we make this an induction on $n$, then (knowing what the final answer looks like) we want to delete $2$ vertices from a graph with this property. To apply the inductive hypothesis, we want to do it in such a way that in the remainder, every vertex still has degree at least $n-1$. Then, by the inductive hypothesis, the remainder has at least $2(n-1)$ vertices; together with the vertices we deleted, the original graph must have at least $2n$ vertices.
Now there is only one thing you need to figure out to make this work. How to choose two vertices to remove from such a graph, so that every degree in the remainder doesn't go below $n-1$?