Let $G$ be an undirected simple graph with $n\leq9$ vertices and each vertex has $m\geq3$ neighbours. Show that $G$ has a cycle of length $\leq4$.
My first idea was to just assume that $G$ has exactly $9$ vertices and each vertex has exactly $3$ neighbours. If the statement is true for $n=9$, then it must be true for $n<9$, too, same thing for $m>3$. How can I now show mathematically, that $G$ with $n=9$ and $m=3$ actually contains a cycle of length $\leq4$?
The claim is false if we allow graphs with $n=0$ vertices. So to proof the claim, we may assume $n\ge1$, each vertex has degree $\ge 3$, all cycles have length $\ge 5$, and from this we try to show that $n>9$.
Pick a vertex $v$, and from its at least three neighbours pick $w_1,w_2,w_3$. For each $w_i$, pick two neighbours $u_{i,1}, u_{i,2}$ distinct from $v$. Note that $u_{i,j}\ne w_k$ as otherwise we'd have a cycle of length $3$. Also, $u_{i,j}\ne u_{i',j'}$ for $(i',j')\ne(i,j)$ because otherwise, we'd have a cycle of length $4$. Thus the ten vertices $$ v,w_1,w_2,w_3,u_{1,1},u_{1,2},u_{2,1},u_{2,2},u_{3,1},u_{3,2}$$ are pairwise distinct, and so $n\ge10$.