Spanning tree

A spanning tree for a graph includes all of its vertices. So it contains the full set of vertices and a subset of the arcs.

If the graph has n vertices then a spanning tree must have n-1 arcs.

This formalises the concept of connectedness: in a spanning tree, for every pair of vertices there is a path between them comprising just arcs from the spanning tree.