In the mathematical field of graph theory, a spanning tree T of a connected, undirected graph G is a tree that includes all of the vertices and some or all of the edges of G.

## Defination

A tree is a connected undirected graph with no cycles. It is a spanning tree of a graph G if it spans G (that is, it includes every vertex of G) and is a subgraph of G (every edge in the tree belongs to G). A spanning tree of a connected graph G can also be defined as a maximal set of edges of G that contains no cycle, or as a minimal set of edges that connect all vertices.