Prueba $P_m X P_n$ es hamiltoniano si y sólo si al menos uno de $m,n$ es incluso

Question

Cómo probar "Probar $P_m X P_n$ (producto cartesiano del gráfico) es hamiltoniano si y sólo si al menos uno de $m,n$ es uniforme"

El producto cartesiano de la gráfica es la gráfica de la rejilla, si averiguo $P_2 X P_2$ será $C_4$ (es hamiltoniano). ¿Cómo se puede demostrar esto?

Answer 1

Si al menos uno de $m$ y $n$ es par, puedes subir y bajar alternativamente en esa dirección, dejando una fila de la otra dirección para completar el ciclo. Un ejemplo en arte ASCII:

/\ /\ /\
|| || ||
|| || ||
| V  V |
\------/

Si ambos $m$ y $n$ son Impares, el número total de vértices es impar, y si los compruebas en blanco y negro un ciclo hamiltoniano tiene que conectar igual número de cada color, lo que es imposible ya que hay diferentes números de ellos porque la suma es impar.