Polynomially reduce Hamiltonian Cycle Existence to Spanning Tree $T$ such that $\deg v \le k$

Question

Problem $1$:

Given a simple graph $G=(V,E)$, Does $G$ have a Hamiltonian cycle?

Problem $2$:

Given a simple graph $G=(V,E)$ and an integer $k$, Does $G$ have a spanning tree like $T$ such that the degree of each vertex of $T$ is at most $k$?

---

Question:

Assume that Problem $1$ is NP-Complete. Prove that Problem $2$ is also NP-Complete. (Provide a translation function)

---

Note: At first, I was thinking of passing $(G,k)$ as the output of the translation function... But that clearly does not work...I'm struggling with finding the appropriate $k$ and the modification of $G$ which does the trick. Unfortunately, I don't even get the idea of reduction in this case...

Thanks in advance.

Answer 1

The Hamiltonian Cycle Problem can be polynomially reduced to the Restricted Spanning Tree Problem with an additional condition on vertex degrees in the following way.

To solve HCP for graph $G$ one can take each edge $e \in E(G)$ in turn, subdivide this edge twice (i. e., replace the path $P_2$ by a path $P_4$) and remove the middle of resulting three edges, build in the new graph $H(e)$ a spanning tree of maximum degree $k = 2$. If for some edge $e$ there is such tree, that is a Hamiltonian path $P$, then removing both end vertices of $P$ (that have degree $1$ in graph $H$) and combining residual with $e$ we get a Hamiltonian cycle. If for each $e$ there is no such spanning tree in $H(e)$ then graph $G$ is not Hamiltonian.

Edit. Initial approach was missing essential details of the edge subdivision, therefore was wrong for example for $K_{2,3}$ saying it to be Hamiltonian.