Soruyu çizge teorisi kavramların kullanarak yeniden formüle edelim: Bir çizgenin her bir köşesi $0,1, \ldots, 2017$ renklerinden birine, her kenarın uçlarındaki köşeler farklı renkte olacak şekilde boyanmış ise bu boyamaya düzgün boyama diyelim. Bir düzgün boyamada, $x$ köşesinin rengi $f(x)$ ile gösterilmek üzere, herhangi $a$ ve $b$ köşeleri için, her $i=1, \ldots, n-1$ için $\left|f\left(x_i\right)-f\left(x_{i+1}\right)\right|=1$ olacak şekilde $a=x_1, x_2, \ldots, x_n=b$ yolu bulunuyorsa bu boyamaya süper düzgün boyama diyelim. Soruda bizden göstermemiz istenen şu soruya denktir:
Bağlantılı bir $G$ çizgesinin düzgün boyaması varsa, süper düzgün boyaması da vardır.
$G$ düzgün boyanmış bir çizge olsun. G'nin süper düzgün boyamaya sahip en büyük alt çizgesi $G_1$ olsun. Biz $G_1=G$ olduğunu göstereceğiz. Aksini varsayalım. Bir $H$ çizgesinin köşeler kümesi $V(H)$, kenarlar kümesi $E(H)$ ile gösterilsin.
$$
\min _{(x, y) \in E(G), x \in V\left(G_1\right), y \in V\left(G-G_1\right)}(|f(x)-f(y)|)=\left|f\left(x_0\right)-f\left(y_0\right)\right|
$$
olsun. Tanımlara göre $\left|f\left(x_0\right)-f\left(y_0\right)\right|>1$ 'dir. Ilk önce, $f\left(x_0\right)>f\left(y_0\right)$ kabul edelim. $G-G_1$ çizgesinde $f\left(y_0\right)$ renkli köşeleri $f\left(x_0\right)-1$ rengine ve $f\left(x_0\right)-1$ renkli köşeleri $f\left(y_0\right)$ rengine boyayalım. Bu yeniden boyama işleminden sonra elde edilen boyamanın da düzgün olacağını gösterelim: $G-G_1$ alt çizgesinde $f\left(x_0\right)-1$ ve $f\left(y_0\right)$ renkleri yer değiştirmiştir ve sonuç olarak herhangi iki komşu köşe farklı renklerde olacaktır. Ayrıca, $\left|f\left(x_0\right)-f\left(y_0\right)\right|$ ifadesinin minimum olmasından dolayı yeniden boyamadan sonra $f(x) \neq f(y)$ koşulu tüm $x \in G_1$ ve $y \in G-G_1$ köşeleri için sağlanacaktır. $f\left(x_0\right)<f\left(y_0\right)$ simetrik durumunda da $G-G_1$ alt çizgesinde $f\left(y_0\right)$ renkli köşeleri $f\left(x_0\right)+1$ rengine ve $f\left(x_0\right)+1$ renkli köşeleri $f\left(y_0\right)$ rengine boyarsak benzer şekilde düzgün bir boyama elde edeceğiz. $G_1$ çizgesine $y_0$ köşesinin ve $y_0$ ile $G_1$ arasındaki tüm kenarların eklenmesiyle oluşan çizge $G_2$ olsun. Bu yeni boyama $G_2$ için bir süper düzgün boyamadır ve $G_2$ alt çizgesi $G_1$ alt çizgesini kapsamaktadır, çelişki. O halde $G_1=G^{\prime}$ dir ve bu da $G$ 'nin bir süper düzgün boyamaya sahip olduğunu gösterir.
Kaynak: Tübitak Çözüm Kitapçığı
