I am trying to solve the following exercise:
Let $G = (V,E)$ be a graph. Show that the following two problems are NP-hard:
- $G$ has a spanning tree where every node has at most $k$ neighbors, and $k$ is part of the input.
- $G$ has a spanning tree where every node has at most 5 neighbors.
It's written that 1 is supposed to be a hint for 2. You can of course choose to ignore it and solve 2 directly.
I tried to reduce $k$-MST to Steiner tree, but I don't know if this is a right way. I read that can use a Hamiltonian circuit, but I don't understand how. Can anybody help me?
