[proofplan] We reduce the Hamiltonian cycle decision problem to the travelling salesman decision problem. Given an undirected graph $G$, we build a complete weighted graph on the same vertex set by assigning distance $1$ to original edges and distance $2$ to non-edges, then set the target bound to the number of vertices. A Hamiltonian cycle in $G$ gives a tour of length exactly $n$, while any tour of length at most $n$ must use only distance-$1$ edges and therefore recovers a Hamiltonian cycle in $G$. Since the construction is polynomial-time and Hamiltonian cycle is NP-complete, this proves NP-hardness. [/proofplan]

[step:Define the polynomial-time reduction from Hamiltonian cycle] Let $\operatorname{HAMCYCLE}$ denote the decision problem whose input is a finite undirected graph $G = (V,E)$ and whose answer is yes exactly when $G$ contains a cycle visiting every vertex of $V$ exactly once. We use the standard [Hamiltonian cycle NP-completeness theorem](/page/Hamiltonian%20Cycle%20Problem), which states that $\operatorname{HAMCYCLE}$ is NP-complete. Let $\operatorname{HAMCYCLE}_{\geq 3}$ denote the restricted decision problem whose input is a finite undirected graph $G = (V,E)$ with $|V| \geq 3$ and whose answer is yes exactly when $G$ contains such a cycle. This restricted problem is also NP-complete: membership in NP is inherited from $\operatorname{HAMCYCLE}$, and NP-hardness follows because the identity map handles inputs with $|V| \geq 3$, while each input with $|V| < 3$ is a no-instance and can be sent to the fixed no-instance $H_0 := (\{a,b,c\},\varnothing)$ of $\operatorname{HAMCYCLE}_{\geq 3}$. Let $\operatorname{Inst}(\Pi)$ denote the set of inputs of a decision problem $\Pi$. Define the reduction map \begin{align*} R: \operatorname{Inst}(\operatorname{HAMCYCLE}_{\geq 3}) &\to \operatorname{Inst}(\operatorname{TSP}_{\mathrm{dec}}) \end{align*} by the construction below. Given an instance $G = (V,E)$ of $\operatorname{HAMCYCLE}_{\geq 3}$, write \begin{align*} V = \{v_1,\dots,v_n\} \end{align*} with $n := |V|$. Since $n \geq 3$, the constructed travelling salesman instance has at least three cities, so its cyclic tour objective is defined in the usual way. We construct an instance $R(G)$ of $\operatorname{TSP}_{\mathrm{dec}}$ with city set $\{1,\dots,n\}$ and bound $K := n$. Define the distance map $d_G: \{\{i,j\} : 1 \leq i < j \leq n\} \to \mathbb{N}$ as follows: for $1 \leq i < j \leq n$, set $d_G(\{i,j\}) := 1$ if $\{v_i,v_j\} \in E$, and set $d_G(\{i,j\}) := 2$ if $\{v_i,v_j\} \notin E$. Thus every distance is a positive integer, and in fact every distance lies in $\{1,2\}$. The reduction map $R$ is computable in polynomial time: it creates $n$ cities and computes one distance for each of the $\binom{n}{2}$ unordered pairs of cities by checking whether the corresponding unordered pair of vertices is an edge of $G$. [/step]

[step:Convert a Hamiltonian cycle into a travelling salesman tour of length $n$] Assume that $G$ is a yes-instance of $\operatorname{HAMCYCLE}_{\geq 3}$. Then there exists a cyclic ordering \begin{align*} (v_{i_1}, v_{i_2}, \dots, v_{i_n}) \end{align*} of the vertices of $G$ such that \begin{align*} \{v_{i_r},v_{i_{r+1}}\} \in E \end{align*} for every $r \in \{1,\dots,n\}$, where $i_{n+1} := i_1$. Consider the travelling salesman tour \begin{align*} (i_1,i_2,\dots,i_n) \end{align*} in the instance $R(G)$. By the definition of $d_G$, each edge of this tour has distance $1$. Therefore its total length is \begin{align*} \sum_{r=1}^{n} d_G(\{i_r,i_{r+1}\}) = \sum_{r=1}^{n} 1 = n = K. \end{align*} Hence $R(G)$ is a yes-instance of $\operatorname{TSP}_{\mathrm{dec}}$. [/step]

[step:Convert any travelling salesman tour of length at most $n$ into a Hamiltonian cycle]Assume that $R(G)$ is a yes-instance of $\operatorname{TSP}_{\mathrm{dec}}$. Then there exists a cyclic ordering \begin{align*} (i_1,i_2,\dots,i_n) \end{align*} of $\{1,\dots,n\}$ such that, with $i_{n+1} := i_1$, \begin{align*} \sum_{r=1}^{n} d_G(\{i_r,i_{r+1}\}) \leq n. \end{align*} Each summand is either $1$ or $2$, so each summand is at least $1$. Since there are exactly $n$ summands, we have \begin{align*} n \leq \sum_{r=1}^{n} d_G(\{i_r,i_{r+1}\}) \leq n. \end{align*} Therefore equality holds throughout, and every summand must be equal to $1$. By the definition of $d_G$, this means \begin{align*} \{v_{i_r},v_{i_{r+1}}\} \in E \end{align*} for every $r \in \{1,\dots,n\}$. Since $(i_1,\dots,i_n)$ is a cyclic ordering of all cities, the cyclic sequence \begin{align*} (v_{i_1},v_{i_2},\dots,v_{i_n}) \end{align*} visits every vertex of $G$ exactly once and uses only edges of $G$. Hence it is a Hamiltonian cycle in $G$.[/step]

[guided]Assume that the constructed travelling salesman instance $R(G)$ has a tour of length at most $n$. This means there is a cyclic ordering \begin{align*} (i_1,i_2,\dots,i_n) \end{align*} of the city set $\{1,\dots,n\}$ such that, with $i_{n+1} := i_1$, \begin{align*} \sum_{r=1}^{n} d_G(\{i_r,i_{r+1}\}) \leq n. \end{align*} The key point is that the tour has exactly $n$ edges, and every one of those edges has distance at least $1$. Therefore \begin{align*} \sum_{r=1}^{n} d_G(\{i_r,i_{r+1}\}) \geq \sum_{r=1}^{n} 1 = n. \end{align*} Combining this lower bound with the assumed upper bound gives \begin{align*} n \leq \sum_{r=1}^{n} d_G(\{i_r,i_{r+1}\}) \leq n. \end{align*} Hence the total length is exactly $n$. Now each individual summand $d_G(\{i_r,i_{r+1}\})$ belongs to $\{1,2\}$. If even one summand were equal to $2$, then the sum of the $n$ summands would be at least \begin{align*} 2 + \sum_{r=1}^{n-1} 1 = n+1, \end{align*} contradicting the equality of the total length with $n$. Therefore \begin{align*} d_G(\{i_r,i_{r+1}\}) = 1 \end{align*} for every $r \in \{1,\dots,n\}$. By the definition of $d_G$, the equality $d_G(\{i_r,i_{r+1}\}) = 1$ is equivalent to \begin{align*} \{v_{i_r},v_{i_{r+1}}\} \in E. \end{align*} Thus the cyclic sequence \begin{align*} (v_{i_1},v_{i_2},\dots,v_{i_n}) \end{align*} uses only edges of $G$. Because $(i_1,\dots,i_n)$ is a cyclic ordering of $\{1,\dots,n\}$, this sequence visits every vertex of $G$ exactly once. Hence it is a Hamiltonian cycle in $G$.[/guided]

[step:Conclude NP-hardness from the reduction] The previous two steps prove that, for every input $G$ of $\operatorname{HAMCYCLE}_{\geq 3}$, \begin{align*} G \in \operatorname{HAMCYCLE}_{\geq 3} \iff R(G) \in \operatorname{TSP}_{\mathrm{dec}}. \end{align*} The map $R$ is computable in polynomial time, so this is a polynomial-time many-one reduction \begin{align*} \operatorname{HAMCYCLE}_{\geq 3} \leq_p \operatorname{TSP}_{\mathrm{dec}}. \end{align*} Since $\operatorname{HAMCYCLE}_{\geq 3}$ is NP-complete, it is NP-hard. Therefore $\operatorname{TSP}_{\mathrm{dec}}$ is NP-hard. Moreover, the constructed instances use only distances in $\{1,2\}$, so the stronger $\{1,2\}$-restricted travelling salesman decision problem is NP-hard; in particular, NP-hardness holds when all distances are positive integers. [/step]