# Simple Cycle Graph proof

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

• Is $n$ even? Because else, $n/2$ is not an integer. Or do you mean the floor of $n/2$? – frabala Apr 3 '14 at 1:18
• – Hubble Apr 3 '14 at 1:22

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}$.)