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.
[Math] Help with graph induction question
graph theoryinduction
Best Answer
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.)