I'm preparing for exams and for my algorithms course we've been needing to cover NP completeness but we never had any real tutorials for them and just got given a pile of "practice questions" for the exam. I've worked through all but the last and I'm really not sure how to solve it (and asking the internet so far has returned published papers I don't understand).
The previous 2 questions were showing that the Hamiltonian Path problem is in the class NP and then show that it was NP-complete by showing that the Hamiltonian Cycle problem reduces to it.
This then leads in to the 3rd question where I can't seem to make headway:
A degree-constrained spanning tree of a graph is a spanning tree of maximum degree k (each vertex in the tree is adjacent to at most k edges) for some fixed k. Deciding whether a graph G contains a spanning tree with degree constrained by k = 2 is the Hamiltonian Path problem, which is an NP-complete problem, as you have just shown. Show that deciding whether a graph G contains a spanning tree with degree constrained by k, for general k, is also an NP-complete problem.
My current attempt at answering this has been along the lines of:
For k = 2, for any vertex V we can split the graph in to 2 distinct sub graphs that only share vertex V and return true for a Hamiltonian Path. That, for k=3, there is a vertex V for which we can split the graph in to 3 distinct sub graphs that all have Hamiltonian Paths.
I know this isn't correct but I feel it is along the right path but not sure how to get to the end goal at all. Any help would be appreciated.