25th Turkish Mathematical Olympiad

Let us reformulate the problem in terms of the graph theory. Let $G$ be a connected graph. Suppose that each vertex of $G$ can be properly coloured into one of colors $0,1,\dots ,2017$: endpoints of each edge are differently coloured. Let $f(x)$ be a color of the vertex $x$. Prove that there is a proper recolouring of vertices of $G$ into colors $0,1,\dots ,2017$ such that

(t) For any two vertices $a$ and $b$ there is a path $a=x_1,x_2,\dots ,x_n=b$ such that for each $i=1,\dots ,n-1$ we have $|f(x_i)-f(x_{i+1})|=1$.

Consider any proper colouring of $G$. Let $G_1$ be a maximal subgraph of $G$ satisfying (t). Let us show that by recolouring of some vertices we can increase the number of vertices of $G_1$. For any graph $G^{\prime }$ the set of vertices of $G^{\prime }$ will be denoted by $V(G^{\prime })$. Let $$m_i{n}_{x\in V(G_1),y\in V(G-G_1)}(|f(x)-f(y)|)=|f(x_0)-f(y_0)|,$$ By definitions $|f(x_0)-f(y_0)|>1$. Suppose that $f(x_0)>f(y_0)$. Let us recolour some vertices of $G-G^{\prime }$: vertices coloured $f(y_0)$ into $f(x_0)-1$ and vertices coloured $f(x_0)-1$ into $f(y_0)$. It can be easily shown after this recolouring the graph is still properly coloured. Indeed, in $G-G_1$ we just switched colors $f(x_0)-1$ and $f(y_0)$. Also note that since $|f(x_0)-f(y_0)|$ is minimal after this recolouring the condition $f(x)\ne f(y)$ still holds also for all $x\in G_1$ and $y\in G-G_1$. In the symmetric case $f(x_0)<f(y_0)$ we will also recolour vertices of $G-G^{\prime }$: vertices coloured $f(y_0)$ into $f(x_0)+1$ and vertices coloured $f(x_0)+1$ into $f(y_0)$.

Thus, after the recolouring the set $V(G_1)$ will be grown by at least one new element $y_0$. By continuing this process eventually we will get desired colouring of whole $G$ satisfying (t).