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?
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$.
"The maximum-leaf spanning tree problem in cubic graphs is NP-complete."
IMA publication no. 428, University of Minnesota, Mineapolis, 1988.
External links referenced by this document: