Complexité d'un autre problème de circuit hamiltonien

Question

Toutes les références que je trouve sur un autre problème de circuit hamiltonien:

Compte tenu d'un graphique et d'un circuit hamiltonien dessus, y a-t-il un autre circuit hamiltonien dessus?

J'essayais de le réduire au problème du circuit hamiltonien, mais j'ai toujours besoin d'ajouter trop ou trop de circuits à celui d'origine.

Est-ce que je passe dans la bonne direction? Cela semble être très simple ...

Éditer

Le livre de complexité de Papadimitriou fait référence à son théorème 17.5 pour l'inspiration de ce problème.

Je pense qu'un bon moyen pour la solution est de considérer le graphique proposé dans Papadimitrious '

On peut pour chaque nœud du graphique d'origine, transformez le graphique illustré à l'image gauche. Ensuite, on peut connecter tous ces nouveaux graphiques à l'aide des pôles n et s et obtient ainsi un circuit hamiltonien. Ensuite, on utilise W et E pour connecter les sommets qui ont été connectés dans le graphique d'origine. En principe, on pourrait se connecter W avec W et E avec E.

Je n'ai qu'un doute de plus, ce qui se passe si le graphique d'origine n'est qu'un segment, c'est-à-dire deux sommets avec un bord entre eux. Ma construction donnerait un circuit hamiltonien supplémentaire allant de W1-> e1-> e2-> w2-> w1 Même si l'original n'en avait pas!

Pouvez-vous trouver un autre contre-exemple? C'était la solution donnée dans mon cours et cela semble être en partie faux ...