Graph contains triangle

Question

Prove that if a simple graph of order n has more than n^2/4 edges then it contains a triangle.

I know Martels theorem states the opposite condition for a triangle free graph but I'm not sure how to prove this condition.

Answer 1

Let $G$ be a simple graph of order $n$. Then Mantel's Theorem states that:

If $G$ is triangle-free, then $G$ has at most $n^2/4$ edges.

But by taking the contrapositive of this implication, we get exactly what we want:

If $G$ has more than $n^2/4$ edges, then $G$ contains a triangle.

Answer 2

Let $G$ be a graph of order $n$ and size $m$. Assume that $G$ is $K_3$-free. Then by Mantel's Theorem we know that $m\leq {n^2\over 4}$. However, this is a contradiction since we are given that $m> {n^2\over 4}$. Thus if $G$ has order $n$ and $m>{n^2\over 4}$, then $G$ contains a triangle.