Let $G$ be a graph with $n\ge3$ vertices and more than $n^2/4$ edges.

I have to prove that G contains a triangle.

I thought to use induction. Base cases are: $n=3, n=4,$ but when I start my induction I get confused...


  • $\begingroup$ What does the problem say about when $n$ is odd? Because $\frac {n^2}4 $ does not make sense in that case. $\endgroup$ – Riccardo Ceccon Jun 3 '18 at 8:56
  • $\begingroup$ Just seen the edit! :) $\endgroup$ – Riccardo Ceccon Jun 3 '18 at 8:56

Proof. (By induction on $n$). If $n<0$, the claim is vacuously true.

Assume $n\ge0$ and $G$ has $n$ vertices and $e$ edges where $e>\frac{n^2}4$. Then also $e>\frac{n^2+1}4>0$. Pick an edge $ab$. If each of $a,b$ has $\ge \frac{n+1}2$ neighbours, they have a neighbour $c$ in common, which leads to a triangle $abc$ and we are done. Hence we may assume that there is a vertex $v$ with $\le \frac{n}2$ neighbours. Removing $v$ and its edges from $G$, we end up with a graph $G'$ with $n-1$ vertices and with at least
$$e-\frac n2>\frac{n^2+1}4-\frac{n}2 =\frac{n^2-2n+1}{4}=\frac{(n-1)^2}4$$ edges. By induction hypotheses, $G'$ has a triangle, which is also a triangle in $G$. $\square$


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.