The spanning tree of a graph (G) is a subset of G that covers all of its vertices using the minimum number of edges.
Some properties of a spanning tree can be deduced from this definition:
Since “a spanning tree covers all of the vertices”, it cannot be disconnected.
A spanning tree cannot have any cycles and consist of edges (where is the number of vertices of the graph) because “it uses the minimum number of edges”.
A graph can have more than one spanning tree. In fact, a complete graph can have a maximum of spanning trees.
View all Courses