Minimum spanning tree
![A planar graph and its minimum spanning tree. Each edge is labeled with its weight, which here is roughly proportional to its length.](/Images/godic/202501/27/Minimum_spanning_tree.svg3934.png")
![This figure shows there may be more than one minimum spanning tree in a graph. In the figure, the two trees below the graph are two possibilities of minimum spanning tree of the given graph.](/Images/godic/202501/27/Multiple_minimum_spanning_trees.svg3934.png")
![This figure shows the cut property of MSTs. T is the only MST of the given graph. If S = A,B,D,E, thus V-S = C,F, then there are 3 possibilities of the edge across the cut(S,V-S), they are edges BC, EC, EF of the original graph. Then, e is one of the minimum-weight-edge for the cut, therefore S ∪ e is part of the MST T.](/Images/godic/202501/27/Msp-the-cut-correct.svg3934.png")
A minimum spanning tree is a spanning tree of a connected, undirected graph. It connects all the vertices together with the minimal total weighting for its edges.
A single graph can have many different spanning trees. We can also assign a weight to each edge, which is a number representing how unfavorable it is, and use this to assign a weight to a spanning tree by computing the sum of the weights of the edges in that spanning tree. A minimum spanning tree (MST) or minimum weight spanning tree is then a spanning tree with weight less than or equal to the weight of every other spanning tree. More generally, any undirected graph (not necessarily connected) has a minimum spanning forest, which is a union of minimum spanning trees for its connected components.