Problem

Source: X International Festival of Young Mathematicians Sozopol 2019, Theme for 10-12 grade

Tags: combinatorics, graph theory, clique



Let $n$ be a natural number. The graph $G$ has $10n$ vertices. They are separated into $10$ groups with $n$ vertices and we know that there is an edge between two of them if and only if they belong to two different groups. What’s the greatest number of edges a subgraph of $G$ can have, so that there are no 4-cliques in it?