algorithm graph graph-algorithm minimum-spanning-tree

It is possible for a graph to have multiple minimum spanning trees

Let G=(V, E) be an undirected graph, all whose edges have a unique weight. Is it true that G has a single unique MST? Or can G also have multiple MSTs?

Solution

As per the definition of MST (source: wikipedia) -

A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight.

The goal is to cover all vertices while having the lowest edge weight sum. Also, a spanning tree (ST) is a tree, so no cycles -

In the image above, the orange trees are STs, but, only the top one can be an MST (edge weight sum is 7).

EDIT

Proof by contradiction:

Let $G(V,E)$ be an undirected graph with unique edge weights. Let $T_1$ and $T_2$ be two distinct Minimum Spanning Trees for the graph.

Let $e_1$ be the edge with lowest weight present in $T_1$ , but, not in $T_2$ . Similarly, let $e_2$ be the edge in $T_2$ , but, not in $T_1$ .

Now, since edge weights are unique, without loss of generality, let $w(e_1)<w(e_2)$ .

Also, if we add $e_1$ in $T_2$ , a cycle will form with $e_2$ . To remove the cycle, let us remove the edge $e_2$ from $T_2$ . Thus, we have a Spanning Tree $T = T_2 U e_1 / e_2$ .

This ST, $T$ , now has total weight less than $T_2$ ; but, this is a contradiction, since, $T_2$ was already an MST.

Thus, our assumption that, $G(V,E)$ had two MSTs to begin with was wrong. This concludes the proof.