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.

Yes, this problem is indeed $$\text{NP}$$-hard.
• 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