spanning tree

A subset of a connected graph's edges that links all V vertices together with no cycles, using exactly V minus one edges.

In more detail

Removing any edge from a spanning tree disconnects it, and adding any edge creates a cycle. A graph usually has many spanning trees; the minimum spanning tree is the one with the smallest total weight.

Related terms

Taught in

References