Prove simple graph with conditions on vertices and edges contains triangle 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
 A: There is a well-known Turán's theorem.
A: Let $G=(V,E)$ be a triangle-free simple graph with $|V|=2n$ vertices; I'll show that $|E|\le n^2$. Let $A$ be an independent set of vertices of maximum cardinality, i.e., $|A|=a$ is as big as possible; and let $B=V\setminus A$, so that $|B|=b=2n-a$. Since $G$ is triangle-free, the neighborhood of any vertex is an independent set, and so $d(v)\le a$ for each vertex $v$. Inasmuch as $d(v)\le b$ for each $v\in A$, and $d(v)\le a$ for each $v\in B$, the degree-sum is at most $2ab$, and so the number of edges is $|E|\le\dfrac{2ab}2=ab\le\dfrac{(a+b)^2}4=\dfrac{(2n)^2}4=n^2$.
A: Let $G$ be a graph with $v$  vertices and $e$ edges.
We show by induction on $v$ that $4e>v^2$ implies the existence of a triangle.
Let $a$ be a vertex of degree $\rho$. Then $G-a$ has $v-1$ vertices and $e-\rho$ edges.
If $\rho<\frac v2$, we find $4(e-\rho)>4e-2v$, i.e. $e(e-\rho)\ge 4e-2v+1>v^2-2v+1=(v-1)^2$ and by induction find a triangle in $G-a$.
Therefore we may assume that the degree of each vertex is $\ge \frac v2$.
Let $a$ be a vertex, let $A$ be the set of $a$'s neighbours and $B=V\setminus A$.
Then we have just schown that $|A|\ge\frac v2$.
Any edge within $A$ would make a triangle with $a$, hence all neighbours of vertices in $A$ are in $B$ and hence $|B|\ge \frac v2$.
We conclude $|A|=|B|=\frac v2$ and each vertex in $A$ has an edge to each vertex in $B$.
Thus any edge within $B$ would make a triangle.
We conclude thet $G$ is bipartite and has exactly $|A|\cdot |B|=\frac{v^2}2$ edges, contradicting $4e>v^2$.$_\square$
A: The result actually predates Turan's theorem. It was proved by Mantel. See http://planetmath.org/mantelstheorem and https://www.dpmms.cam.ac.uk/~dc340/EGT1.pdf
