Let $G=(V,E)$ be a simple $k$-regular graph (which means that every vertex in $G$ has $k$ neighbors). Moreover, G doesn't contain any triangles or any cycles with the length of 4. I need to prove that there are at least $k^2-k+1$ vertices in $G$.
I started with a vertex $v_0$ which has $k$ neighbors. Then I picked one of them. let's say $v_1$. $v_1$ has $k-1$ neighbors other than $v_0$ but they don't have any mutual neighbors (otherwise there will be a triangle). Then I pick again one of $v_1$'s neighbors, let's say $v_2$, which also doesn't have any mutual neighbors with the previous two vertices (otherwise there will be a triangle or a cycle). I pick again one of $v_2$'s neighbor, let's say $v_3$.
I thought i will go on like that until I get to the needed amount of vertices (since every vertex has $k$ neighbors), but here I got stuck.