A simple $n$-regular graph with no cycles of length $>3$ has at least $2n$ vertices

Question

Let $H$ be a simple graph that has no cycles of length more than $3$. Each vertex has degree of $n$. Is it possible to prove $H$ has at least $2n$ vertices?

Answer 1

Consider an arbitrary node $x$. Now, consider the set of $k$ neighbors of $x$, denoted by $N(x)$. Now, let's consider another arbitrary node $y \in N(x)$. Clearly, if $z \in N(y)$, then $z \not \in N(x)$, because otherwise $x, y, z$ would form a 3-cycle. Thus $N(x)$ is disjoint with $N(y)$. Since both $N(x)$ and $N(y)$ consists of $k$ elements, we have $2k$ nodes at minimum.

Answer 2

Consider $u\in V(G)$. We know that $N[u]=k+1$ since $G$ is $k$-regular. None of $u$'s neighbors are adjacent since $G$ is triangle-free. So all the vertices in $N(u)$ are adjacent to $k-1$ vertices in $G-N[u]$ and $|G-N[u]|\geq k-1$. Thus $|G|=|N[u]|+|G-N[u]|\geq (k+1)+(k-1)=2k$.