No obstante, los ciclos y caminos actualmente denominados hamiltonianos aparecieron mucho antes.Podemos, no obstante, anotar algunas condiciones necesarias para que un grafo sea hamiltoniano.La mejor aportación en este sentido es un teorema publicado en 1976 debido a J. A. Bondy y a V. Chvátal, que generaliza los resultados anteriormente encontrados por G. A. Dirac (1952) y Ø. Ore (1960).Todos estos resultados afirman, básicamente, que un grafo es hamiltoniano si existen “suficientes aristas”.[7] Se puede consultar una demostración directa del Teorema de Ore en [Theorem 6.2.5[3]].Consideremos el siguiente grafo, al que se suele denominar como “grafo casa”, que es claramente hamiltoniano:Una consecuencia del Teorema de Ore es el resultado siguiente.Si G es un grafo simple, sin lazos y con n vértices en el cual grado(u) + grado(v) ≥ n − 1 para todo par de vértices u, v, entonces G no es necesariamente hamiltoniano.Esto se aprecia en muchos ejemplos; en particular, en los siguientes.Para grafos dirigidos mencionemos un resultado de H. Meyniel que proporciona también una condición suficiente para que un dígrafo fuertemente conexo sea hamiltoniano.Si D es un grafo dirigido fuertemente conexo de n vértices en el cual grado(u) + grado(v) ≥ 2n − 1 para toda pareja u, v de vértices no adyacentes entonces D es grafo dirigido hamiltoniano.
Un ciclo hamiltoniano en el grafo de un dodecaedro. El grafo del dodecaedro es hamiltoniano como el resto de grafos de sólidos platónicos
