Revision as of 08:14, 27 November 2005 edit Dcoetzee (talk \| contribs) 37,529 edits m dab ← Previous edit		Revision as of 08:18, 27 November 2005 edit undo Dcoetzee (talk \| contribs) 37,529 edits For k=2, is Hamiltonian path problem Next edit →
Line 7: Question: Does G have a spanning tree in which no node has degree greater than ''k''? This problem is [[NP-Complete]]. 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 (in fact, for ''k''=2, this is the Hamiltonian path problem). == References ==

Degree-constrained spanning tree: Difference between revisions