Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Minimum degree spanning tree
open-in-new
<p>In <a href="/facts/Graph_theory/VVPCd4TX">graph theory</a>, a minimum degree spanning tree is a subset of the edges of a <a href="/facts/Connectivity_(graph_theory)/FSNjsYhz">connected</a> graph that connects all the <a href="/facts/Vertex_(graph_theory)/WhlWmL3o">vertices</a> together, without any <a href="/facts/Cycle_(graph_theory)/Is44edrv">cycles</a>, and its maximum degree of its vertices as small as possible. That is, it is a <a href="/facts/Spanning_tree/qQPN9taR">spanning tree</a> whose maximum degree is minimal. </p><p>The decision problem is: Given a graph <i>G</i> and an integer <i>k</i>, does <i>G</i> have a spanning tree such that no vertex has degree greater than <i>k</i>? This is also known as the <a href="/facts/Degree-constrained_spanning_tree/XCYJLXdb">degree-constrained spanning tree</a> problem. </p>