**Possible multiplicity**
*There may be several minimum spanning trees of the same weight*; in particular, if all weights are the same, every spanning tree is minimum.

**Uniqueness**

*If each edge has a distinct weight then there will only be one, unique minimum spanning tree*. This can be proved by induction or contradiction. This is true in many realistic situations, such as the cable TV company example above, where it's unlikely any two paths have *exactly* the same cost. This generalizes to spanning forests as well.

A proof of uniqueness by contradiction is as follows. Say we have an algorithm that finds an MST (which we will call *A*) based on the structure of the graph and the order of the edges when ordered by weight. (Such algorithms do exist, see below.) Assume for the moment that this MST is not unique and that there is another spanning tree, *B*, with equal weight. If there are *n* vertices in the graph, then each tree has *n*-1 edges. There are some edges which belong to *B* but not to *A*. What happens if we decrease the weight of one of these edges by a tiny amount ε so that we do not change the overall ordering of all the edges of the graph when ordered by weight? (This is possible because all weights are separated by positive amounts.) It will not change the result of our algorithm, which still gives tree *A*. But tree *B* will now have a weight ε less than what it had before, which means that *A* is not minimal, contrary to assumption. Because of this contradiction, we conclude that the assumption that there can be a second MST was false.

**Minimum-cost subgraph**

If the weights are *non-negative*, then a minimum spanning tree is in fact the minimum-cost subgraph connecting all vertices, since subgraphs containing cycles necessarily have more total weight.

**Cycle property**

*For any cycle* C *in the graph, if the weight of an edge* e *of* C *is larger than the weights of other edges of* C*, then this edge cannot belong to an MST.* Assuming the contrary, i.e. that *e* belongs to an MST T1, then deleting *e* will break T1 into two subtrees with the two ends of *e* in different subtrees. The remainder of *C* reconnects the subtrees, hence there is an edge *f* of *C* with ends in different subtrees, i.e., it reconnects the subtrees into a tree T2 with weight less than that of T1, because the weight of *f* is less than the weight of *e*.

**Cut property**

*For any cut* C *in the graph, if the weight of an edge* e *of* C *is smaller than the weights of other edges of* C*, then this edge belongs to all MSTs of the graph.* Indeed, assume the contrary, i.e., *e* does not belong to an MST T_{1}. Then adding *e* to T_{1} will produce a cycle, which must have another edge *e*_{2} from T_{1} in the cut *C*. Replacing *e*_{2} with *e* would produce a tree T_{1} of smaller weight.