I know this problem can be done directly but I have tried this using Induction. I want your help in understanding where my proof is wrong.
Proof: We will use induction on n (number of vertices of the graph)
Base step : The graph with the least number of vertices and a girth of 5 is 5-cycle $C_5$. So, we consider this as a base case, as the minimum degree is 2 and clearly $2^2+1 \leq 5$. So base case is satisfied.
Hypothesis : Let this statement be true for all graph having $n-1$ vertices and a girth of 5.
Induction Step : Let G be a graph with n vertices and a girth of 5.
Consider the 5-cycle in G. Now if none of the vertices in this cycle is having other neighbors apart from the cycle itself then we get the base case i.e. 5-cycle itself.
So let $u$ be the vertex in this 5-cycle that has another neighbor, say $v$, that is not in this cycle. (If this is in the cycle then girth will be less than 5)
Case 1 : If $v$ is the vertex with the least degree then removing $v$ will definitely not decrease the minimum degree of the graph and using the induction hypothesis on $G-v$ we are done. (Same hold if $v$ is not attached to the vertex of minimum degree)
Case 2 : If $v$ is attached to the vertex with the minimum degree.
If the minimum degree is $\leq 2$ then we are done as this graph definitely has more than 5 vertices.
If the minimum degree is $> 2$ then there must be anther vertex attached to the selected 5-cycle other than $v$, say $v'$, then we remove this vertex and similar to case 1 we are done.
Note: disconnection will not affect the result.
Please help me to find the mistake if any in the above proof. Thankyou