# Complexity of Minimum Spanning Trees with Lower Degree Bounds

It is known, that the problem of calculating Minimum Spanning Trees with an upper bound on the vertex degrees is NP complete.

Question:

what is the complexity of calculating Minimum Spanning Trees if the set of leaf nodes is given and all other vertex degrees must be greater than a given lower(!) bound $k$, under the condition that the underlying Graph is complete and symmetric and, that the existence of a spanning tree with the given degree constraints exists?

A concrete example would be to calculate a minimum spanning tree of a symmetric graph with $3*(2^n-1) + 1$ vertices of which $3*2^{n-1}$ are defined to be leaf nodes and all other verticex degrees are at least 3 in the spanning tree.