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$.
Problem
Source: V International Festival of Young Mathematicians Sozopol 2014, Theme for 10-12 grade
Tags: combinatorics, clique, graph theory
12.11.2019 14:54
My Mantels theorem, in a $2n$ graph without 3-cycles, $|E| \leq \frac{2014^2}{4} =1007^2$. So we require $\frac{k(k+1)}{2} \leq 1007^2$ or $k^2+k-2 \cdot 1007^2 \leq 0 \implies k \in \frac{-1 \pm \sqrt{1+8 \cdot 1007^2}}{2}$. So $k \leq 1423$.
12.11.2019 16:12
All is well but you also have to show $1423$ is achievable which I guess is the main difficulty of the problem.
13.11.2019 20:30
I claim that the answer is $1342=\lfloor \frac{2*2014}{3} \rfloor$. Let $2014=n$. Consider the vertex with the degree $k$. All of its neighbours have degrees less than or equal to $n-k$ - indeed, since no two of them are connected by the given condition. So, the group of the given neighbours produces at most $n-k$ different degrees from the positive integer set. The second group, made of the rest of $n-1-k$ vertices, produces at most $n-k-1$ different degrees. Since all the vertices produce exactly $k$ different degrees, we have $1+(n-k)+(n-k-1) \ge k,$ thus $k \le \lfloor \frac{2n}{3} \rfloor$. This bound motivates us to construct the following example: Let $t=671,$ we try to construct a graph with $3t+1$ vertices which produce exactly all the degrees from ${1,2,...,2t}$. Take a vertex $X$ and connect it to $2t$ vertices $A_1, A_2, ... , A_{2t}$. Take another set of $t$ vertices $B_1, ... , B_t$. Now connect $A_i$ to vertices $B_1, ..., B_{i-1}$ for all $i=2,3,...,t$. We are finished with the vertices $A_1, A_2, ... , A_t$ having the degrees $1,2,...,t$ in that order. Currently, the vertices $B_1, B_2, ... , B_t$ have the degrees $t-1, t-2, ... , 0,$ respectively. Connect each of them to all the vertices $A_{t+1}, A_{t+2}, ... , A_{2t},$ so that their degrees become $2t-1, 2t-2, ..., t,$ and we are done.