Minimum degree spanning tree

In graph theory, for a connected graph G , a spanning tree T is a subgraph of G with the least number of edges that still spans G . A number of properties can be proved about T . T is acyclic, has ( | V | − 1 ) edges where V is the number of vertices in G etc.

A minimum degree spanning tree T ′ is a spanning tree which has the least maximum degree. The vertex of maximum degree in T ′ is the least among all possible spanning trees of G .

Finding minimum degree spanning tree is NP hard, but a local search algorithm can give a tree which its maximum degree is at most the maximum degree of optimal tree plus one.

See Degree-Constrained Spanning Tree.