Comment:
The 4-degree spanning tree problem also admits a PTAS, but the NP-hardness
of the problem is open [31].
The 5-degree problem is polynomial-time solvable.
In d-dimensional Euclidean space for
the 3-degree spanning tree
problem is approximable within 5/3. [299].
The generalization to a graph with metric weight function and for each
vertex
Ưa degree bound d(v) is called
MINIMUM BOUNDED DEGREE SPANNING TREE and is approximable within
,
where
dT(v) is the initial degree of v [146].