3
$\begingroup$

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)

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

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.

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – user8722 Apr 3 '14 at 18:49
  • $\begingroup$ @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! $\endgroup$ – Barry Cipra Apr 3 '14 at 18:59
  • $\begingroup$ This is an awesome proof Barry. Great answer, +1, simple, slick and clean. $\endgroup$ – Rustyn Apr 3 '14 at 20:20
  • $\begingroup$ 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? $\endgroup$ – Rustyn Apr 3 '14 at 20:29
  • $\begingroup$ 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|$???? $\endgroup$ – Rustyn Apr 3 '14 at 20:39
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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) $\endgroup$ – user8722 Apr 3 '14 at 18:28
  • $\begingroup$ 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. $\endgroup$ – ml0105 Apr 3 '14 at 18:30
  • $\begingroup$ 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? $\endgroup$ – ml0105 Apr 3 '14 at 18:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.