# A question about k-regular graphs

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.

• Why does your question say $k^2\color{red}{-k}+1$ ? – Donald Splutterwit Sep 17 '17 at 20:14

Pick a point $v_0$, it has $k$ neighbours $v_1,v_2,\cdots,v_k$ and none of these can be joined (in order to avoid any "triangles"). Now each of these $k$ points has a further $k-1$ neighbours and each of these points are distinct (in order to avoid any "quadrilaterals"). From the point $v_0$ there are $k$ points in the first shell and $k(k-1)$ points in the second shell, so the graph must have a least $k^2+1$ points.