# NP-hardness of existence of spanning tree with given maximal degree

I am trying to solve the following exercise:

Let $$G = (V,E)$$ be a graph. Show that the following two problems are NP-hard:

1. $$G$$ has a spanning tree where every node has at most $$k$$ neighbors, and $$k$$ is part of the input.

2. $$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?

• Hint for part 1: What does it mean when G has a spanning tree where every node has at most 2 neighbors? – user53923 Dec 4 '17 at 10:35
• @user53923 maybe you mean that for k=2 it s exactly an Hamiltonian path? – theantomc Dec 4 '17 at 11:47
• Also, make sure you are doing the reduction the right way. (That is, to show hardness of an unknown problem X, should you reduce X to e.g., Hamiltonian path, or the other way around?) – Juho Dec 4 '17 at 11:51
• @Antonio exactly – user53923 Dec 4 '17 at 12:12
• @Juho exactly I don't know how do :\ but i know that if want know if my problem is Np-hard i try to reduce my problem X to an another problem Y that is NP-complete. Now I m seeing a Low deegre spanning tree and Bounded-Degree Spanning Tree problem . Unfortunally i don't understand well my first problem, so reduction is more hard to do in this way. – theantomc Dec 4 '17 at 12:51

Hint for part 1: What does it mean when $G$ has a spanning tree where every node has at most 2 neighbors?
Hint for part 2: Suppose you know that it is NP-hard to show that $G$ has a spanning tree where every node has at most 2 neighbors. Can you reduce this problem of at most 2 neighbors to the current problem of at most 5 neighbors?