Misalkan
\(\GVE\) adalah graf yang
\(2\)-dapat diwarnai, dengan fungsi pewarnaannya mempartisi
\(V\) menjadi
\(A\cup B\text{.}\) Karena tidak ada sisi di antara simpul-simpul pada bagian partisi yang sama, setiap siklus dalam
\(\bfG\) harus berselang-seling antara simpul di
\(A\) dan simpul di
\(B\text{.}\) Oleh karena itu, agar siklus tersebut tertutup, banyaknya simpul pada siklus yang berasal dari
\(A\) harus sama dengan banyaknya yang berasal dari
\(B\text{;}\) akibatnya, panjang siklus tersebut genap.
Sekarang andaikan \(\bfG\) tidak memuat siklus ganjil. Perhatikan bahwa kita boleh mengasumsikan \(\bfG\) terhubung, karena setiap komponennya dapat diwarnai secara terpisah. Jarak \(d(u,v)\) antara simpul \(u,v\in V\) adalah panjang lintasan terpendek dari \(u\) ke \(v\text{,}\) dan tentu saja \(d(u,u) = 0\text{.}\) Tetapkan sebuah simpul \(u_0\in V\) dan definisikan
\begin{equation*}
A
= \{v\in V\colon d(u_0,v)\text{ is even}\}\qquad\text{and}\qquad B = \{v\in V\colon
d(u_0,v)\text{ is odd}\}.
\end{equation*}
Kita mengklaim bahwa mewarnai simpul-simpul di \(A\) dengan warna \(1\) dan simpul-simpul di \(B\) dengan warna \(2\) menghasilkan pewarnaan tepat. Andaikan tidak demikian. Maka, tanpa mengurangi keumuman, terdapat simpul \(x,y\in A\) sedemikian sehingga \(xy\in E\text{.}\) Karena \(x,y\in A\text{,}\) \(d(u_0,x)\) dan \(d(u_0,y)\) keduanya genap. Misalkan
\begin{equation*}
u_0,x_1,x_2,\dots,x_n=x
\end{equation*}
dan
\begin{equation*}
u_0,y_1,y_2,\dots,y_m= y
\end{equation*}
merupakan lintasan terpendek dari \(u_0\) masing-masing ke \(x\) dan \(y\text{.}\) Jika \(x_i\neq y_j\) untuk setiap \(1\leq
i\leq n\) dan \(1\leq j\leq m\text{,}\) maka karena \(m\) dan \(n\) keduanya genap,
\begin{equation*}
u_0,x_1,x_2,\dots,x_n=x,y=y_m,y_{m-1},\dots,y_2,y_1,u_0
\end{equation*}
merupakan siklus ganjil dalam \(\bfG\text{,}\) yang bertentangan dengan asumsi. Jadi, harus ada \(i,j\) sedemikian sehingga \(x_i=y_j\text{,}\) dan kita dapat memilih \(i,j\) sebesar mungkin. (Artinya, setelah \(x_i=y_j\text{,}\) kedua lintasan tersebut tidak berpotongan lagi.) Dengan demikian,
\begin{equation*}
x_i,x_{i+1},\dots,x_n = x,y=y_m,y_{m-1},\dots,y_j=x_i
\end{equation*}
merupakan siklus dalam \(\bfG\text{.}\) Berapa banyak simpul yang terdapat dalam siklus ini? Perhitungan singkat menunjukkan bahwa siklus tersebut memiliki
\begin{equation*}
n-(i-1)+m-(j-1)-1=n+m-(i+j)+1
\end{equation*}
simpul. Kita mengetahui bahwa \(n\) dan \(m\) genap, dan perhatikan bahwa \(i\) dan \(j\) keduanya genap atau keduanya ganjil, sebab \(x_i = y_j\text{,}\) sementara simpul-simpul lintasan kita yang berindeks ganjil berada di \(B\) dan yang berindeks genap berada di \(A\text{.}\) Jadi, \(i+j\) genap, sehingga \(n+m-(i+j)+1\) ganjil, yang menghasilkan kontradiksi.
