El uso de la inducción. Deje $v$ ser un vértice en $G$. Color correctamente $G \setminus \{v\}$ con $\ell$ colores $0,1,2,\ldots \ell-1$. Consideramos dos casos.
Caso 1: Todos los de $\ell$ colores son utilizados para $N_G(v)$. A continuación, elija un color arbitrario $k$, y un vecino de la $w$ de $v$. Cambio $w$'s de color a $k-1$, y a su vez todos los de $w$'s vecinos de colores $k-1$, a $k-2$, y así sucesivamente y así sucesivamente [aritmética hecho de mod $\ell$], que termina cuando no hay más vértices de la izquierda para cambiar los colores. Entonces, si este proceso termina en un número finito de pasos que el resultante para colorear es todavía una adecuada coloración. Pretendemos que ningún vértice $u$ en $G \setminus \{v\}$ obtiene cambia de color dos veces. [De hecho, la única manera de que un vértice $u$ (de color $k'$ en el original para colorear decir) podría ser repintadas dos veces sería si en el original para colorear hay un camino de $P$ de $j\ell+1$ vértices; $j$ un entero positivo tal que $P$ comienza a $u$ y también (a) escribir $P = uu_1\ldots u_{j\ell}$, vértice $u_r$ era de color $k'-r$ en el original para colorear, y (b) $u_{j\ell}$ es adyacente a $u$. Pero, a continuación, $u$ e $u_{j\ell}$ habría dado el mismo colorante $k'$ en el original para colorear, contradiciendo la suposición de que el original para colorear fue la correcta.[Por no mencionar, que contradice la suposición de que no hay ciclos de longitud $j\ell+1$ en $G$]] por Lo que el proceso, de hecho, termina en un número finito de pasos y por lo tanto la resultante de nueva coloración es adecuada.
Además, pretendemos que ningún vértice en $N_G(v)$ que no estaba de color $k$ antes de que en el original para colorear, obtener colores $k$. [De hecho, si hubiera un vértice $w' \in N_G(v)$ entonces $w'$ hubiera sido asignado $k+1$ en el original para colorear. Por lo tanto, utilizando una línea similar de razonamiento como en el párrafo anterior, esto implicaría un camino de $P$ de $j\ell$ vértices en $G \setminus \{v\}$ con un extremo como $w$ y el otro extremo de $w'$, que no implica que es un ciclo de longitud 1 mod $\ell$ en $G$; es decir $P$ además de los dos bordes de la $w'v$ e $vw$].
Por lo tanto, podemos repetir el proceso en los dos anteriores párrafos hasta lograr una adecuada coloración de $G \setminus \{v\}$ donde no hay vértices en $N_G(v)$ color $k$, y luego se le asigna el color de $k$ a $v$.
Caso 2: no es un color $k$ en $0,1,\ldots, \ell-1$ de tal manera que ningún vértice en $N_G(v)$ es de color $k$. A continuación, asigne $v$ color $k$.
Esta respuesta fue reforzada por bof la observación de que en el cambio de color a ningún vértice sería cambia de color dos veces, incluso si hay ciclos de longitud $j\ell+1$.
