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!

  • 2
    $\begingroup$ 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. $\endgroup$
    – kabenyuk
    Nov 9, 2022 at 3:43


You must log in to answer this question.

Browse other questions tagged .