Minimum degree spanning tree
Encyclopedia
In graph theory
, for a connected graph
, a spanning tree
is a subgraph of 
with the least number of edges that still spans 
. A number of properties can be proved about 
. 
is acyclic, has (
) edges where 
is the number of vertices in 
etc.
A minimum degree spanning tree
is a spanning tree which has the least degree. The vertex of maximum degree in 
is the least among all possible spanning trees of 
.
See Degree-Constrained Spanning Tree.
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
, for a connected graph
, a spanning treeSpanning tree (mathematics)
In the mathematical field of graph theory, a spanning tree T of a connected, undirected graph G is a tree composed of all the vertices and some of the edges of G. Informally, a spanning tree of G is a selection of edges of G that form a tree spanning every vertex...
is a subgraph of with the least number of edges that still spans . A number of properties can be proved about . is acyclic, has () edges where is the number of vertices in etc.A minimum degree spanning tree
is a spanning tree which has the least degree. The vertex of maximum degree in is the least among all possible spanning trees of .See Degree-Constrained Spanning Tree.