Minimum degree spanning tree

In graph theory, for a connected graph [math]\displaystyle{ G }[/math], a spanning tree [math]\displaystyle{ T }[/math] is a subgraph of [math]\displaystyle{ G }[/math] with the least number of edges that still spans [math]\displaystyle{ G }[/math]. A number of properties can be proved about [math]\displaystyle{ T }[/math]. [math]\displaystyle{ T }[/math] is acyclic, has ([math]\displaystyle{ |V|-1 }[/math]) edges where [math]\displaystyle{ V }[/math] is the number of vertices in [math]\displaystyle{ G }[/math] etc. A minimum degree spanning tree [math]\displaystyle{ T' }[/math] is a spanning tree which has the least maximum degree. The vertex of maximum degree in [math]\displaystyle{ T' }[/math] is the least among all possible spanning trees of [math]\displaystyle{ G }[/math].

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.