<p>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>

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

<ul>
<li>Lemke's result implies the NP-completeness of deciding whether there exists a spanning tree without vertices of degree $2$.</li>
<li>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$. </li>
<li>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\}$.</li>
</ul>

CC BY-SA 4.0
2018-05-25T08:54:51.907Z
2018-05-25T08:54:51.907Z
Gamow
<p>I am teaching a complexity course, and I want to give some examples of similar looking problems such that one is in P, and the other is NP complete.</p>

<p>This made me think of the following problem: does a given graph contain a spanning tree with a given degree sequence? This is obviously easy for the sequence $n-1,1,...,1$ and hard for $2,...,2,1,1$.  Is there a general answer?</p>

<cc.complexity-theory><np-hardness><np>
NP completeness of classes of spanning trees
Zur Luria
# NP completeness of classes of spanning trees

(Asked by: username_0 on 2018-05-25)

I am teaching a complexity course, and I want to give some examples of similar looking problems such that one is in P, and the other is NP complete.

This made me think of the following problem: does a given graph contain a spanning tree with a given degree sequence? This is obviously easy for the sequence $n-1,1,...,1$ and hard for $2,...,2,1,1$. Is there a general answer?

**Tags:** cc.complexity-theory, np-hardness, np


---

## 1 answers

### Answer by username_1 on 2018-05-25. Score: 5 | Accepted answer

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\}$.


---

