Graph Concepts

Spanning trees

A spanning tree of a graph is a subgraph that contains (or "spans") every vertex of the original graph.

Because it is a tree, a spanning tree is connected and has no cycles. Because it is connected, the graph must be connected.

The spanning tree of this graph is red.

A minimal spanning tree is often of interest when a weighted graph is used to model a problem. If the graph is weighted, the weight of a spanning tree is the sum of the weights of all of its edges. The minimal spanning tree is the spanning tree whose weight is the smallest of all possible spanning trees that you could draw for that graph.

The minimal spanning tree for this graph is red.