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 grado 1, automáticamente sabemos que no puede ser hamiltoniano.
Para saber si un grafo es Hamiltoniano o no, debemos aplicar el Teorema de Dirac, que se enuncia: "Sea G = (V,E) un grafo conexo con |V| ≥ 3.
Para facilitar la comprensión del mismo podríamos ver el Teorema de Dirac del modo siguiente: Sea un grafo al que llamaremos G, con sus vértices y aristas, conexo, y con n.º total de vértices mayor o igual a 3.
Es decir, el grafo a tratar debe cumplir todas estas características para poder continuar aplicando el Teorema, si no las cumple entonces no será Hamiltoniano.