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

Question

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

Thanks!

Answer 1

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$