- INSTANCE:
Set
of points in the plane.
- SOLUTION:
A spanning tree
*T*for*P*in which no vertex has degree larger than 3. - MEASURE:
The total weight of the spanning tree, i.e.,
,
where
*d(u,v)*is the Euclidean distance between*u*and*v*.

*Good News:*Admits a PTAS [33].*Comment:*The 4-degree spanning tree problem also admits a PTAS, but the NP-hardness of the problem is open [33]. 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. [316].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 is the initial degree of*v*[158].