Spanning tree

For the network protocol, see Spanning Tree Protocol. For other uses, see Spanning tree (disambiguation).
A spanning tree (blue heavy edges) of a grid graph

In the mathematical field of graph theory, a spanning tree T of an undirected graph G is a subgraph that is a tree which includes all of the vertices of G.[1] In general, a graph may have several spanning trees, but a graph that is not connected will not contain a spanning tree (see about spanning forests below). If all of the edges of G are also edges of a spanning tree T of G, then G is a tree and is identical to T (that is, a tree has a unique spanning tree and it is itself).

  1. ^ "Tree". NetworkX 2.6.2 documentation. Retrieved 2021-12-10. For trees and arborescence, the adjective "spanning" may be added to designate that the graph, when considered as a forest/branching, consists of a single tree/arborescence that includes all nodes in the graph.