Minimum degree spanning tree

From Wikipedia, the free encyclopedia

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 degree. The vertex of maximum degree in T' is the least among all possible spanning trees of G.

See Degree-Constrained Spanning Tree.

This article does not cite any references or sources. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed. (April 2009)