---
tag: 0S4ZEZM7KE
kind: concept
name: Spanning tree
msc: [05C05]
sources:
  - url: https://en.wikipedia.org/wiki/Spanning_tree
    locator: Definitions
same_as:
  wikidata: Q831672
  wikipedia: Spanning tree
---

## Summary

A spanning tree of a graph is a tree inside the graph that reaches every vertex. Spanning trees are the minimal connected spanning subgraphs, with uses in network design and in counting. The node [[spanning tree|0FQ5B8S1ZC]] gives the precise definition.