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.

  • $\begingroup$ Why does your question say $k^2\color{red}{-k}+1$ ? $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.