Suponemos que $G$ era no hamiltoniano y añadía todas las aristas posibles a $G$ para que el gráfico resultante $H$ es no hamiltoniano. Sea $x$ y $y$ sean dos vértices no adyacentes de $H$ tal que $H+xy$ es hamiltoniano. Vemos que todo ciclo hamiltoniano de $H+xy$ debe contener la arista $xy$ . Así, $H$ contiene un Hamiltoniano $x-y$ camino $P=(x=x_1,x_2,...,x_n=y)$ . Afirmamos que siempre que $x_1x_i$ es una arista de $H$ , donde $2\leq i\leq n$ entonces $x_{i-1}x_n$ no es una arista de $H$ , de lo contrario podemos producir un ciclo hamiltoniano en $H$ lo cual es imposible ya que $H$ es no hamiltoniano. Por lo tanto, se deduce que para cada vértice en $\{x_2,x_3,..,x_n\}$ que es adyacente a $x_1$ hay un vértice en $\{x_1,x_2,...,x_{n-1}\}$ que no es adyacente a $x_n$ lo que implica que $\deg x_n\leq (n-1)-\deg x_1$ y así $\deg_Hx+\deg_Hy\leq n-1$ . Por tanto, se ha producido una contradicción y $G$ es hamiltoniano.
La demostración de este teorema no es evidente a primera vista. Cuando la afirmación de "siempre que $x_1x_i$ es una arista de $H$ , donde $2\leq i\leq n$ entonces $x_{i-1}x_n$ no es una arista de $H$ ", tenemos que pensar realmente en los vértices que se permiten y no se permiten ser adyacentes a $x=x_1$ y $y=x_n$ . La razón es que en $H$ tenemos un Hamiltoniano $x-y$ y si $x_n$ es adyacente a $x_{i-1}$ cuando $x_1$ es adyacente a $x_i$ , donde $2\leq i\leq n$ entonces hemos producido un ciclo hamiltoniano en $H$ que es imposible. Por lo tanto, para cada vértice de $\{x_2,x_3,..,x_n\}$ que es adyacente a $x_1$ hay un vértice en $\{x_1,x_2,...,x_{n-1}\}$ que no es adyacente a $x_n$ . Además, sabemos que cada vértice en $H$ tiene un grado menor o igual a $n-1$ . Por lo tanto, como sabemos que $x_n$ no es adyacente a $x_1$ desde $H$ es no hamiltoniano, entonces $\deg x_n\leq (n-1)-\deg x_1$ lo que implica que $\deg_Hx+\deg_Hy\leq n-1$ lo que contradice el hecho de que $\deg u+\deg v\geq n$ para cada par $u$ , $v$ de vértices no adyacentes de $G$ . Así, $G$ es hamiltoniano.
