The Euclidean degree-4 minimum spanning tree problem is NP-hard
Andrea Francke, Michael M. Hoffmann · 2009
We show that it is an NP-hard problem to decide for a given set P of n points in the Euclidean plane and a given parameter k∈R, whether P admits a spanning tree of maximum vertex degree four whose sum of edge lengths does not exceed k.