# Help with graph induction question?

Given a graph $G$ with $n$ vertices, where $n$ is even, prove by induction that if every vertex has degree $n/2 + 1$, then $G$ must contain a 3-cycle. A 3-cycle is a set of 3 vertices, $a; b; c$ such that $ab$ is an edge, $bc$ is an edge and $ac$ is an edge.

-
You might want to add the graph-theory tag. –  Chris Godsil Mar 25 '13 at 22:11

HINT: Suppose not, and let $G$ be a minimal counterexample. Let $G$ have $2m$ vertices, each of degree greater than $m$. Let $v$ be any vertex of $G$, and let $w$ be any vertex such that $vw$ is an edge. Let $G'$ be the graph that remains after you remove the vertices $v$ and $w$ and all edges incident at them. Use the fact that $G$ contains no triangle to show that for each vertex $u$ of $G'$, $$\deg_{G'}(u)\ge\deg_G(u)-1\ge m-1$$ and get the contradiction that $G$ wasn’t actually a minimal counterexample.

(You can recast this as a proof by induction on $m$ in the usual style, if you want; it’s the same proof either way, with almost identical details.)

-
I understand why its true, but i cant seem to do it with induction. I just dont know how i would put a counterexample in a induction proof. –  Zain Mar 25 '13 at 22:19
@Zain: It’s the same thing: as far as I’m concerned, the argument that I outlined is a proof by induction. But if you really want to recast it in the traditional style, get the induction off the ground with $m=1$ (two vertices). Now assume that it’s true for $2(m-1)$ vertices, and use my argument to show that it must be true for $2m$ vertices: if there were a counterexample with $2m$ vertices, that argument would give a counterexample with $2(m-1)$ vertices, contradicting the induction hypothesis (or, in my version, the assumption that my counterexample was minimal). –  Brian M. Scott Mar 25 '13 at 22:22
@BrianM.Scott Can you explain the reasoning behind degG′(u)≥degG(u)−1≥m−1, is this the core contradiction? What is the significance of degG', degG - 1, and m-1. How are you able to conclude that degG' >= degG - 1? –  GivenPie Nov 27 '13 at 5:08
@BrianM.Scott Does the contradiction arise based on the handshaking lemma? Even amount vertices with odd degree is even? –  GivenPie Nov 27 '13 at 17:13
@GivenPie: There’s a typo in my last comment, as you can see if you compare it with the answer: it should say that $\deg_{G'}(u)\ge\deg_G(u)-1$. The two degrees may be equal for some vertices of $G'$, since there’s no reason to think that every vertex of $G'$ was connected to $v$ or $w$, but the important thing is that it cannot be less than $\deg_G(u)-1$, since $u$ is definitely not connected to both $v$ and $w$. –  Brian M. Scott Nov 27 '13 at 20:02

Proof by induction means proving a base case and then proving that if true for x it is true for x +1. Since we are only interested in in even numbers of vertices that would mean proving that if true for n vertices it is also true for n + 2 vertices.

Given graph G with n vertices where n is even and greater than 3 and every vertex has (n/2)+1 edges.

Our base case is n = 4. With n = 4 each vertex has (4/2)+1 = 3 edges. This means that every vertex is connected to every other vertex by an edge. Thus any combination of 3 vertices will be a 3 cycle.

Inductive step. If true for n = k then true for n = k+2.

With k vertices: each of the k vertices has (k/2)+1 edges attached to it and each edge connects 2 vertices so the graph as a whole has (k((k/2)+1))/2 total edges in it. A graph with k+2 vertices will increase the number of edges in the graph by (((k+2)(((k+2)/2)+1))/2) - ((k((k/2)+1))/2). (the number in the larger graph - number in the smaller graph). We can simplify this to k+2 additional edges in the graph.

Since our graph with k vertices had a 3-cycle (our inductive assumption) we must remove at least one of those edges from that graph. Each vertex, except the 2 new ones and the two connected by the edge we removed, need one new edge attached to them. The two vertices that were connected by the edge we removed need 2 new edges, and the two new vertices will each need ((k+2)/2)+1 new edges.

Adding the edge removed from the graph with k vertices to the number of additional edges that we have to add, we need to add k+3 edges to the graph. If we add a new edge between any of the original k vertices we will be creating a 3-cycle. (we have accepted as true that with all the edges in a graph of k a 3-cycle was created, even if the edge removed broke the only one 3-cycle then a new one would be formed by placing an edge somewhere else among the original k vertices). Since we can't place a new edge between any 2 of the original k vertices each of them must connect to one of the new vertices. If we connect each of the original k vertices to one of the new vertices we have placed k of the edges and have 3 edges left to place. The two vertices that were connected by the edge we removed and the two new vertices are the only ones that can accept a new edge. Each of the two vertices that were part of the orignal k vertices can only accept one edge and each is connected to at least one of the two new vertices. We are left with 4 vertices we can connect edges to and 5 edges connecting those 4 vertices (the 3 we haven't placed plus the 2 already placed between the old and new vertices) plus we can't connect the two old vertices together. 5 edges placed among 4 vertices means that while 2 of the 4 are connected to only two other vertices the other 2 vertices are connected to all 3 of the other vertices and those two will create an 3 cycle with on of the other two.

Proof complete.

Someone else may be able to write it out clearer but it is all here.

-
The statement is true even for $n=2$, because there is no simple graph on $2$ vertices with degree $2$, thus no possible counterexample. –  Erick Wong Mar 26 '13 at 2:13
I see what you are saying, with formal logic if A then B is always true if A is false. Also I forgot that unqualified designation of graph usually means simple graph. I will edit my answer. –  Edward Goodson Mar 26 '13 at 2:21
@EdwardGoodson: It really helps readability to format using MathJax (see FAQ). Regards –  Amzoti Mar 26 '13 at 2:27
What you are calling a proof by induction is only one kind of proof by induction. Structural induction is another, and indeed is the most appropriate kind here. And all of them can be stated in terms of minimal counterexamples, as in my answer. –  Brian M. Scott Mar 26 '13 at 3:48
@Amzoti Thanks for the info. on MathJax I hadn't found that yet. Brian, I did not intend any comment on your answer with my answer. I did find the article on structural induction very interesting. –  Edward Goodson Mar 26 '13 at 6:17