I'm trying to prove : Given a simple graph $G$ with $n$ vertices, where $n$ is even, prove that if every vertex has degree $\dfrac n2 + 1$, then $G$ must contain a (simple) $3$-cycle. A (simple) $3$-cycle is a set of $3$ (distinct) vertices, $a, b, c$ such that $ab$ is an edge, $bc$ is an edge and $ac$ is an edge.
I know there are similar ones already on here, but I can't comprehend any of the answers. This is what I have so far:
Base Case: Since the graph has to have at least $3$ vertices to have a simple $3$-cycle, the lowest possible even number of vertices is $n = 4$.
$\dfrac42 + 1 = 3$ degree (edges attached to node). This means each vertex connects to each of the other $3$ vertices since $G$ is a simple graph. Thus, any combination of $3$ vertices will be a simple $3$-cycle.
Inductive Hypothesis: Assume a simple graph with $k$ vertices, where $k$ is even, contains a simple $3$-cycle if each vertex has degree $\dfrac k2 + 1$.
Inductive Step: Since only concerned about when the graph has an even number of vertices, going to show a simple graph with $k + 2$ vertices, where $k$ is even, contains a simple $3$-cycle if every vertex has degree $\dfrac{k+2}{2} + 1$
This is as far as I get and don't know how to finish the Inductive Step
(Also please feel free to let me know if I messed anything up, up to this point)
Best Answer
You don't really need induction for this. Let $u$ and $v$ be adjacent vertices, and let $U$ and $V$ be the sets of $n/2$ other vertices adjacent to $u$ and $v$ respectively. Since $|U|+|V|+|\{u,v\}|=n+2$ is greater than $n$, we must have $U\cap V\not=\emptyset$. So in fact we've proved more, namely that if each vertex in a graph on $n$ vertices (with $n$ even) has degree $n/2+1$, then every pair of adjacent vertices is part of a triangle.