# Maximum edges in graph with no triangles is complete bipartite

I know that Mantel's theorem says that the maximum number of edges in a graph with no 3-cycles is $\lfloor n^2/4\rfloor$. How can I prove that a graph with no 3-cycles and the maximum number of edges is necessarily $K_{\lfloor n/2 \rfloor , \lceil n/2 \rceil}$?

I have tried assuming equality in the inductive proof of Mantel's theorem, so for any edge, its endpoints together are incident with EXACTLY k−1 other edges, so proving the inductive hypothesis provides equality rather than an upper bound, but I am lost on how to go further.

You can show that if $G$ has the maximum edges on $n$ vertices and no $3$-cycles, then for any three vertices $x,y,z$ if edge $xy$ exists, then either $xz$ or $yz$ exists. This implies you should be looking at complete bipartite graphs.

From there show $K_{n/2,n/2}$ maximizes edges among complete bipartite graphs. (I'm not sure how to get ceiling and floor functions)

• Thank you, but I am looking to derive this from Mantel's theorem Sep 23 '15 at 2:21
• The above is essentially a proof of mantel's theorem as it is easy to find the number of edges in a complete bipartite graph, so this technique proves mantel's theorem and answers your question in one shot.
– Ben
Sep 23 '15 at 2:30
• How about an odd cycle with length $>3$? Sep 23 '15 at 4:57
• @NP-hard This question has some answers for that. I'm not sure if there is a nice result like the $C_{3}$ where we know exactly which graph attains the maximum, as the proof idea I gave is a special case of Turan's theorem for complete graphs, since $C_{3} = K_{3}$.
– Ben
Sep 23 '15 at 5:55
• @Ben: $\lfloor x \rfloor$ is \lfloor x \rfloor; $\lceil x \rceil$ is \lceil x \rceil. Both can be autosized; e.g., $\left\lfloor\frac{n}2\right\rfloor$ is \left \lfloor \frac{n}2 \right \rfloor. Sep 23 '15 at 14:46