# Help with graph induction proof

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)

• This is just Mantel's theorem, which is a special case of Turan's theorem. – ThePortakal Apr 3 '14 at 18:57

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.

• wow... mind clearing up everything after "n+2 is grater than n". Clearly get everything up to and including that but don't understand your conclusions after – user8722 Apr 3 '14 at 18:49
• @user8722, if $U$ and $V$ were disjoint, then $G$ would have at least $n+2$ vertices, which is a contradiction. Consequently, there is a vertex $w$ which is adjacent to $u$ because it's in $U$ and adjacent to $v$ because it's in $V$. Voila! – Barry Cipra Apr 3 '14 at 18:59
• This is an awesome proof Barry. Great answer, +1, simple, slick and clean. – Rustyn Apr 3 '14 at 20:20
• Note that, if degree of each vertex $v_i$ is such that $\frac{n}{2} +1 \le d(v_i) \le n-1$, then this argument holds as well...Question: how many triangles is a pair of adjacent vertices a part of in this case? – Rustyn Apr 3 '14 at 20:29
• We do the same construction, and get that $|U| + |V| + |\{u,v\}|$ = $d(u) -1 + d(v) -1 + 2 \ge n+2$ so that $|U\cap V|\ge 1$ But can we do better than this??? Denote $d(u) = \frac{n}{2}+1+j, d(v)=\frac{n}{2}+1+k$. Thus, $|U|+|V| + |\{u,v\}| = (n+2)+j+k$. Now what is $|U\cap V|$???? – Rustyn Apr 3 '14 at 20:39

So for the inductive step, we construct a graph from $G_{k}$ by adding two new vertices $v_{k+1}$ and $v_{k+2}$ and adding edges such that each vertex has degree $\frac{k+2}{2} + 1$. By the inductive hypothesis, there is already a triangle present in $G_{k}$, so there is a triangle in $G_{k+2}$.

• Is that all you would say if you were answering this question, or is their more stuff I should state?? Just seems too simple (completely agree with it though) – user8722 Apr 3 '14 at 18:28
• I would give a more explicit construction of how to connect $v_{k+1}$ and $v_{k+2}$ to $G_{k}$. I leave the construction for you. However, the way I use the inductive hypothesis is the punchline. – ml0105 Apr 3 '14 at 18:30
• Here is a hint- you may consider removing certain edges from $G_{k}$ to connect them to the two new vertices. If you break a three cycle, will you create a three cycle? – ml0105 Apr 3 '14 at 18:42