Minimum degree spanning tree

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

A minimum degree spanning tree ${\displaystyle T'}$ is a spanning tree which has the least maximum degree. The vertex of maximum degree in ${\displaystyle T'}$ is the least among all possible spanning trees of ${\displaystyle 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.