# Question about Turan Graph Derivation

I am aware that this is fairly similar to previously asked questions, but nowhere seems to specify the method that I am attempting to prove this.

I need to show that for a simple graph $$G$$, if $$\epsilon(G) > \nu(G)^2$$, then $$G$$ contains a triangle. My proof follows:

We know that if G contains no $$K_{m+1}$$, then $$\epsilon(G)\leq \epsilon(T_{2, \nu(G)})$$. Since a triangle is a $$K_3$$, we just need to find $$\epsilon(T_{2, \nu(G)})$$, or the maximum number of edges a graph with no triangles may have.

If $$\nu(G)$$ is even, then $$2|\nu$$. We let $$G$$ have bipartition $$X,Y$$. So $$|X| = |Y| = \frac{\nu}{2}$$. Then the degree of each $$x\in X$$ is $$\frac{\nu}{2}$$, and the degree of each $$y\in Y$$ is $$\frac{\nu}{2}$$. So we have $$\frac{\nu}{2}\bullet\frac{\nu}{2}$$ + $$\frac{\nu}{2}\bullet\frac{\nu}{2}$$ = $$2\epsilon$$, or $$\epsilon = \nu^2/4.$$

I need assistance showing this is true for $$\nu(G)$$ odd. I have tried but I get weird numbers that don't work.

Thank you!

• First, you have a typo. It should be like this: if $\epsilon(G)>ν(G)^2/4$, then $G$ contains a triangle. Second, your reasoning certainly does not prove this statement about triangles. Third, this statement is called Mantel's theorem. Nov 9, 2022 at 3:43