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.