A Hamiltonian cycle of an undirected graph G $=($V$,$ E$)$ is a simple cycle that contains each

vertex in V$.$ The Hamiltonian cycle problem asks $$Does the undirected graph G have a

Hamiltonian cycle?$$

The travelling salesman optimization problem asks $$Given a list of cities and the distances

between each pair of cities, what is the shortest possible route that visits each city exactly

once and returns to the origin city?$$

$(1)$ States a decision version of the travelling salesman problem. $[5$ marks$]$

$(2)$ Provide a reduction from the Hamiltonian cycle problem to the travelling salesman

decision problem, and justify it$.[5$ marks$]$

$(3)$It is known that the Hamiltonian cycle problem belongs to the NP$-$complete problems.

Prove or disprove that the travelling salesman decision problem is NP$-$complete.