The number of cliques of size $4$ where all the edges are of the same colour is at most $\frac{\binom{n}{4}}{3^5}.$

Let $K_n$ be the complete graph on $n$ vertices. Prove that for all integers $n \ge 4$, we can assign each edge one of $3$ colours such that the number of cliques of size $4$ where all the edges are of the same colour is at most $$\frac{\binom{n}{4}}{3^5}.$$

Can someone give some hints? I am not able to see the problem.

There are $\binom{n}{2}$ edges in $K_n$.

Solution 1:

Fix an arbitrary $4$-clique and a uniformly chosen edge coloring with at most $3$ colors. The clique has $\binom{4}{2}=6$ edges, and so the probability that it is monochromatic is $3/3^6$. By linearity of expectation, the expected number of monochromatic $4$-cliques is $\binom{n}{4}3/3^6=\binom{n}{4}/3^5$. So there exists a coloring with at most (and also one with at least) that many monochromatic $4$-cliques.