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.
Best Answer
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)