When proving NP-completeness do I only need one instance of a problem or all of them?
When you reduce Hamiltonian-Path (HP) to Spanning-Tree-with-inner-degree-$k$ (ST), you show that if you could solve ST then you could solve HP, and moreover in a specific way. If the resulting tree is not completely general, say it is always a Hamiltonian path with attached leaves, then you are actually proving the stronger result that the corresponding promise problem is already NP-hard.

A promise problem is one in which it is guaranteed that the input is either a Yes instance or a No instance, and the task is to distinguish only those two cases. In your case, the promise version is defined in this way:


Yes instance: the graph contains a spanning tree formed by a Hamiltonian path backbone and $k-2$ leaves attached to all internal vertices;
No instance: the graph contains no spanning tree in which the degrees of all internal vertices are $k$.


If a graph falls into neither class, we don't care what the answer is. Your proof shows that it is NP-hard to distinguish the Yes instances from the No instances.

We usually don't formulate NP-hardness results this way since it is more cumbersome, but you're right that the proof shows something more. However, if you only cared about the NP-hardness of ST, then there is no need for the reduction to potentially produce all Yes instances of ST. This is because the proof that the reduction implies NP-hardness of ST doesn't require this feature. Here is the proof:


  Suppose $A$ is NP-hard, and $f$ is a polynomial time reduction from $A$ to $B$ such that $x \in A$ iff $f(x) \in B$. Since $A$ is NP-hard, for every $L$ in NP there exists a polynomial time reduction $g$ such that $x \in L$ iff $g(x) \in A$, and so $x \in L$ iff $f(g(x)) \in B$. Since $x \mapsto f(g(x))$ is also polynomial time, this shows that $B$ is NP-hard.


At no point of this proof do we use anything about the possible instances produced by $f$.



Another situation in which we can conclude an improved result is when the instance (rather than the solution) has a specific form. Suppose, for example, that we were able to reduce HP to ST, and the resulting graph never has triangles (I'm not claiming that this is possible; this is just for illustration). In this case, we could conclude also that ST-for-triangle-free-graphs is also NP-hard. It still remains true that ST itself is NP-hard; if a special case is NP-hard, then the general case is a fortiori NP-hard.