Problema del ciclo hamiltoniano

En teoría de grafos, el Problema del ciclo hamiltoniano y el Problema del camino hamiltoniano tratan de determinar si un ciclo hamiltoniano o un camino hamiltoniano existen en un determinado grafo. Existe una íntima relación entre ambos, de los que se conoce que son NP-completos. Un ciclo hamiltoniano, es a su vez, un ciclo que pasa una y solo una vez por todos los nodos (vértices) del grafo. Cuando hablamos de grafos ponderados, que poseen pesos o costos en sus aristas, se sabe que el ciclo hamiltoniano de menor costo es a su vez también la solución al problema del viajante (TSP, del inglés Travelling Salesman Problem). Si un grafo (G) tiene un vértice de valencia 1, automáticamente sabemos que no puede ser hamiltoniano.