Minimum degree spanning tree

From Wikipedia, the free encyclopedia

This article is orphaned as few or no other articles link to it. Please help introduce links in articles on related topics. (November 2006)

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.