Simple Cycle Graph proof

Question

How can I show/prove that given a simple graph G with $n$ vertices, where $n$ is even, that if every vertex has degree $\frac{n}{2} + 1$, then G must contain a (simple) 3-cycle

Answer 1

Pick a vertex $v$. It has $\tfrac{n}{2}+1$ neighbours and thus $n-(\tfrac{n}{2}+1)=\tfrac{n}{2}-1$ non-neighbours.

If $u$ is a neighbour of $v$, then it has a common neighbour with $v$ (together inducing a $3$-cycle), otherwise its $\tfrac{n}{2}$ neighbours other than $v$ belong to the set of $\tfrac{n}{2}-1$ non-neighbours of $v$, which is a contradiction.

(Also note the bound it tight, since $K_{n/2,n/2}$ has no triangles and every vertex has degree $\tfrac{n}{2}$.)