1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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)

$\endgroup$
6
  • $\begingroup$ Thank you, but I am looking to derive this from Mantel's theorem $\endgroup$
    – shane
    Sep 23 '15 at 2:21
  • $\begingroup$ 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. $\endgroup$
    – Ben
    Sep 23 '15 at 2:30
  • 1
    $\begingroup$ How about an odd cycle with length $>3$? $\endgroup$
    – PSPACEhard
    Sep 23 '15 at 4:57
  • $\begingroup$ @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}$. $\endgroup$
    – Ben
    Sep 23 '15 at 5:55
  • 1
    $\begingroup$ @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. $\endgroup$ Sep 23 '15 at 14:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.