# Spanning tree with chosen leaves NP-Complete proof

I want to prove that the problem described here

Spanning tree with chosen leaves

is NP-Complete.

Of course it is in NP, but what problem would be appropriate to reduce to prove NP-Hardness? And how would that work?

• This is my bad. I am fully aware. I am just a bit tired maybe because I am currently studying reductions, and I was so sure that this was an NP-complete problem, so I didn't even see the answers to the topic. :( Sorry for that! Your answer fully makes sense, thank you! – kopsti Feb 3 '16 at 2:39
• Just a comment on terminology: you might end up with a spanning forest instead of a spanning tree if you designate a set of leaves. For example, just consider a path where some middle vertex is designated as a leaf. – G. Bach Feb 3 '16 at 9:34