# minimum spanning tree

Given a graph $G$ with weighted edges, a minimum spanning tree is a spanning tree with minimum weight, where the weight of a spanning tree is the sum of the weights of its edges. There may be more than one minimum spanning tree for a graph, since it is the weight of the spanning tree that must be minimum.

For example, here is a graph $G$ of weighted edges and a minimum spanning tree $T$ for that graph. The edges of $T$ are drawn as solid lines, while edges in $G$ but not in $T$ are drawn as dotted lines.