# 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

• As with another question you asked, this question is of low quality. It is phrased in a way that suggests you copied it directly from an assignment - which is acceptable, but you should indicate which assignment! Otherwise, there is no way to tell what level the answer should be written at. Moreover, you have not described any attempt you have made at solving the question. – Carl Mummert Jun 16 '13 at 16:09
• We a group of interested sit together to solve problems which we found.My friend gave me this and I had no clue how to approach.I am in first yr of my UG. We do it just to enjoy math and don't really pay attention to language or phrasing.Please help me with that.I wont mind If you edit it for me. My English is not good . Thanks – SMath Jun 16 '13 at 16:45
• !sammath: that's fine - all sorts of problems are welcome here. But it helps if you include some context, so that people know what sort of answer to write, and how advanced to make it. And definitely tell what you tried - many times someone will be able to tell you how to make your method work. – Carl Mummert Jun 16 '13 at 16:51
• Ok.I will do it from next time. – SMath Jun 16 '13 at 16:55

## 4 Answers

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

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$

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

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