# Prove finding a spanning tree with no more than 50 leaves is NP-hard

This is a homework question. Consider the problem of finding if an undirected graph $$G$$ can have a spanning tree with no more than 50 leaves. Is this problem NP-hard?

I think it is and I'm trying to prove it. So far I've tried to reduce Vertex Cover to this problem. My idea is that the internal nodes of a spanning tree of $$G$$ form a vertex cover of $$G$$, but I'm stuck at trying to relate the internal nodes to the number of leaves of the spanning tree.

## 1 Answer

Yes, this problem is indeed $$\text{NP}$$-hard.

Here is a hint of proof. Draw several trees with 2 leaves. What kind of graphs are they?

• They are paths. Nov 19, 2021 at 4:10
• Right. There is a problem about finding a path that is also a spanning tree. What is that problem? Nov 19, 2021 at 5:15
• The Hamiltonian path problem? Nov 19, 2021 at 5:39
• I've come up with this. Let $s$ and $t$ be two nodes in $G$. Let $G'$ be a new graph made of $G$ plus 25 new vertices connected to $s$ and $25$ new vertices connected to $t$. Then, then the existence of a Hamiltonian Path in $G$ implies that there is spanning tree in $G'$ with at most 50 leaves. Is this correct? Nov 19, 2021 at 9:30
• Cool, that is correct. Nov 19, 2021 at 9:35