NP completeness of classes of spanning trees

Lemke has shown that it is NP-hard to decide whether a cubic graph on $n=2k$ vertices has a spanning tree in which $k+1$ vertices have degree $1$ and $k-1$ vertices have degree $3$.

P. Lemke:
"The maximum-leaf spanning tree problem in cubic graphs is NP-complete."
IMA publication no. 428, University of Minnesota, Mineapolis, 1988.
https://www.ima.umn.edu/Maximum-Leaf-Spanning-Tree-Problem-Cubic-Graphs-NP-Complete

• Lemke's result implies the NP-completeness of deciding whether there exists a spanning tree without vertices of degree $2$.
• A slight modification of Lemke's reduction shows that the following problem is NP-complete for every fixed integer $p\ge4$: Decide whether there exists a spanning tree, in which every non-leaf vertex has degree at least $p$.
• The same modification shows that the following problem is NP-complete for every fixed integer $p\ge4$: Decide whether there exists a spanning tree, in which every vertex degree lies in $\{1,p\}$.

Solved by user31660 (5,712 )
May 25, 2018 at 08:54