Buenas Nicolás:
En el nuevo grafo puedes aplicar la condición suficiente de existencia de ciclos Hamiltonianos.
El agregado de esas aristas es un invariante en Hamiltonianos (es decir, tanto el grafo anterior como el original son los dos o ninguno Hamiltoniano).
Cordiales saludos,
Pablo.