algorithmgraphgraph-algorithmminimum-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 -

    enter image description here

    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.