Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

spanning
tree
graph
data structures
mst

What is a spanning tree?

Educative Answers Team

​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:

  1. Since “a spanning tree covers all of the vertices”, it cannot be disconnected.

  2. A spanning tree cannot have any cycles and consist of (n1)(n-1) edges (where nn 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 nn2n^{n-2} spanning trees.

svg viewer
Different possible spanning trees

RELATED TAGS

spanning
tree
graph
data structures
mst
Copyright ©2022 Educative, Inc. All rights reserved
RELATED COURSES

View all Courses

Keep Exploring