​The **spanning tree** of a [graph](https://www.educative.io/answers/what-is-a-graph-data-structure) (*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 $(n-1)$ edges (where $n$ 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 $n^{n-2}$ spanning trees.

What is a spanning tree?

​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 (n−1)(n-1)(n−1) edges (where nnn 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 nn−2n^{n-2}n​n−2​​ spanning trees. 