# Maximum number of triangles given fixed number of edges

Consider all graphs with E many edges. The question is to find the maximum number of triangles such a graph can have. The answer is $$O(E^{1.5})$$ and the maximum occurs with it’s a clique.

Now my question is what happens if the size of maximum clique is fixed, i.e., I cannot have a clique of full size to maximize triangles. Then, under this constraint, how does the optimizer graph (one with maximum triangles) look like?

The claim I have is that the graph should be a union of multiple cliques of appropriate size. But I cannot prove that the maximizer is Union of cliques of appropriate sizes who are independent of each other.

• What exactly is 'this'? What do you mean precisely by 'a uniform multiple clique of appropriate size'? Until you make this precise, there isn't much hope of proving this. – Servaes Feb 11 at 8:15
• The graph is Union of multiple cliques of appropriate size which are independent to each other. I don’t know if there is a name for such graphs. Thanks I’m editing the question. – pulpfictional Feb 11 at 8:17
• Your interpretation of the claim is obviously false. Consider the case of 12 edges, maximum clique size 3. A union of independent 3-cliques gets us four triangles. An octahedron gets us eight triangles. – jmerry Feb 11 at 8:36
• In general, it seems reasonable that the $K_r$-free graph with $m$ edges and the most triangles will be approximately a complete balanced $(r-1)$-partite graph. – Misha Lavrov Feb 11 at 23:21