Mongolian Mathematical Olympiad

Suppose that $k\ge 1343$ and denote $A$ a vertex degree of which equals to $1343$.

Let's consider a vertex degree of which is no greater than $672$ and denote it by $B$. Suppose that vertices $A,B$ are connected by an edge. Then from remaining $2012$ vertices $1342$ are connected with $A$ and $671$ are connected with $B$. If we denote $S(A)$ neighbour vertices of $A$ then $671+1342>2012$ and it implies $S(A)\cap S(B)\ne \varnothing$. It means the graph contains a triangle which contradicts given condition.

Suppose that $A,B$ not connected. Since there exist at least $671$ vertices degrees of which are $672,673,\dots ,1342$, there are at least $671$ vertices not connected with $A$. On the other hand the vertex $A$ connected with exactly $1343$ vertices. From this follows $671+1343>2013$ this leads to a contradiction. Thus we conclude $k<1343$. If $k=1342$ then $A$ connected with $B_1,B_2,\dots ,B_{1342}$, $C_1$ with $B_2,B_3,\dots ,B_{1342}$, $C_2$ with $B_3,B_4,\dots ,B_{1342}$, $\dots$ $C_{671}$ with $B_{672},B_{673},\dots ,B_{1342}$ and there is no triangle. Degree of $A$ is $1342$, degree of $C_1$ is $1342$, degree of $C_2$ is $1341$, degree of $C_{671}$ is $672$, degree of $B_1$ is $1$, degree of $B_2$ is $2$, degree of $B_{671}$ is $671$. Thus we have proved that maximal value of $k$ is $1342$.