Ciclo hamiltoniano

A diferencia del caso euleriano, no se conoce una caracterización sencilla: decidir si un grafo es hamiltoniano es un problema NP-completo. Sí hay condiciones suficientes. El teorema de Dirac asegura el ciclo si todo vértice tiene grado al menos \(n/2\), y el de Ore lo asegura si \(\deg(u)+\deg(v)\ge n\) para cada par de vértices no adyacentes.

También hay obstrucciones fáciles de ver. Un vértice de grado 1 lo impide, porque un ciclo necesita dos aristas en cada vértice. Un vértice de corte lo impide también, como en el corbatín. Y en un grafo bipartito las dos partes deben tener igual tamaño, pues el ciclo alterna entre ellas; por eso \(K_{2,3}\) no es hamiltoniano y \(K_{3,3}\) sí.

Ejemplo guía: \(K_n\) con \(n\ge 3\) es hamiltoniano y tiene \((n-1)!/2\) ciclos distintos; el cubo \(Q_3\) lo es mediante el código Gray \(000,001,011,010,110,111,101,100\). Un error típico es creer que ciclo euleriano y hamiltoniano se implican: hablan de aristas y de vértices respectivamente, y ninguno implica al otro.