Complexity of the problem to determine if a spanning tree exists inside a connected graph Given a connected graph G, what is the complexity of the problem to determine if a spanning tree with a number of leaves less or equal to k exists inside G? I don't really know how to determine it and how to reach a proper solution to this.
When $k = 2$, this is just the Hamiltonian path problem, which is known to be NP-complete.