[Math] Prove simple graph with conditions on vertices and edges contains triangle

combinatoricsgraph theory

Let $G$ be a simple graph with $2n$ vertices and more than $n^2$ edges. Then
prove that $G$ must contain a triangle.

Can you find a 'good' condition on the number of edges of
a graph with $3m$ vertices such that $G$ must always contain a complete
$4$-graph?

Note: A triangle is a complete 3-graph

Thanks

Best Answer

There is a well-known Turán's theorem.

Related Question