Problem

Source: V International Festival of Young Mathematicians Sozopol 2014, Theme for 10-12 grade

Tags: combinatorics, clique, graph theory



The graph $G$ with 2014 vertices doesn’t contain any 3-cliques. If the set of the degrees of the vertices of $G$ is $\{1,2,...,k\}$, find the greatest possible value of $k$.