Suppose G is a connected graph with distinct positive intege

Suppose G is a connected graph with distinct positive integer edge weights. Prove that G has exactly one minimum spanning tree T. You may invoke the cut property and/or the cycle property if needed.

Solution

Now I will prove this problem using contradiction method:

For this we have connected graph G.    And the graph have two minimum spanning tree MST1 and MST2 and both contain minimum weight so we will try to prove that MST1! =MST2.
Let’s assume that the graph has 2 MST - MST1 and MST2. Let E be the set of edges present in MST2 but not in MST1.
The MS1 and MST2 have set of (V, E) where V= {v₁, v2, v3……v_n} and E= {e1, e2, e3…en}

And all the edge has distinct positive weights.

Here V-> denote set of Vertex and E->denote set of Edge.

Now we take MST2 (As we assume this is minimum spanning tree), if we add an edge in to MST2 it will create Cycle, Let’s assume that MST2 is not minimum so we add an edge e_nE into MST2 called new Graph G’. So it’s create a cycle into MST2 so our goal is remove an edge from G’ (whose weight is minimum) for converting into spanning three, in other word we are just one egde away to convert G’ into MST.

As we know for finding spanning tree from any Connected Graph (G’), we must remove the edge those weight has minimum , so either existing edge in to the spanning tree(MST2) has minimum weight or the newly added edge e_n contain minimum weight , so we remove the most expensive edge .

*Please note as we assume all edge have distinct weight so there only one weight whose weight is minimum so we remove this edge and the G’ is converted in to Minimum Spanning Tree called MST2.

Here we have two cases:

Explanation: But this case is not practical because we already assume that MST2 is Minimum Spanning Tree, its violet the Minimum Spanning Tree property (ie. All the edge in the Minimum Spanning Tree contain minimum weight)

This case is practical according to the Minimum Spanning Tree all the edges in the MST2 have minimum weight so we can’t add any edge in to Minimum Spanning Tree

So our MST2 is minimum.

As starting point we assume that Graph is connected and all the edge has distinct weight

According to the spanning tree property we construct spanning tree with minimum weight, but we assume that we have two spanning tree with minimum weight,

So our assumption is false, ie MST1=MST2 (Means MST1 and MST2 are same)

Means we can construct only one spanning tree with minimum weight .

Hence Prove