[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$.
[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]
[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]
