Degree Constrained Spanning Tree

Input

Graph $G = (V, E)$, positive integer $K \leq |V|$.

Question

Is there a spanning tree for $G$ in which no vertex has degree larger than $K$?

Classes

• NP-complete

Comments

Remains NP-complete for any fixed $K \geq 2$.

Proofs

NP-complete

Transformation from Hamiltonian Path.

Reducible from

• Hamiltonian Path