This problem is [[NP-Completecomplete]]. This can be shown by a reduction from the [[Hamiltonian path problem]]. It remains NP-complete even if ''k'' is fixed to a value ≥ 2. If you have defined that the degree must be ≤ ''k'', the ''k'' = 2 case of degree-confined spanning tree is the Hamiltonian path problem.
