I ready for taking a P.hD Entrance Exam. one of old-solution problem of Data Structure is as follows:
Which of the following Claims is True about MST of Simple, Undirected, Weighted and Connected Graph G? (edge weights is not necessarily different.)
1) if lightest edge between any cut in G, be unique, then MST is unique.
2)If all edges weights be different, MST is unique.
3) if the weights of e=(u, v) be equal to maximum lightest edge in all paths between u and v then e be in the MST.
Answer: one of them is Correct.
Who can explain more, which is true? why? there is any proof or we must take an example or provide counterexample?
To see that 2 is true, consider two different MSTs $T_1$ and $T_2$; we will show that either $T_1=T_2$ (i.e. they are not different) or one of them is not actually minimal. Since they are both minimum, the sum of each's edge weight is the same. Say the edges of $T_1$ are $e_1 < e_2 < ... < e_n$ and the edges of $T_2$ are $f_1 < f_2 < ... < f_n$. Since the trees are different (by hypothesis) there is (at least) one edge that is different: say $e_i\in T_1$ and $e_i\notin T_2$... choose $e_i$ as the smallest edge with this property i.e. $e_1=f_1, e_2=f_2, ..., e_{i-1}=f_{i-1}$ and $e_{i} < f_{i}$.
Then, add $e_{i}$ to $T_{2}$. You created a cycle, so now we delete an edge to make it a tree. Delete the edge of maximum weight on the cycle, $f_{j}$. Provided that the edge we deleted ($f_j$) isn't $e_{i}$ then the new Tree $T_{2}+e_{i}-f_{j}$ has lower weight than $T_{2}$ and hence $T_{2}$ wasn't a MST (contradiction). Now, we just have to show that $e_{i}$ is not $f_{j}$.
If $e_{i}$ is $f_{j}$ that means that the edge we added was the heaviest edge on the cycle (had largest weight). If this is the case, then every edge on the cycle is lighter and therefore comes earlier in the ordering (i.e. all the edges on the cycle have subscripts smaller than $i$). But, then all these edges are also in $T_1$ and $e_i$ is in $T_1$, but $T_1$ is a tree and contains no cycle. Therefore, there is an edge on the cycle that is not in $T_{1}$ and hence has more weight than $e_{i}$. Thus, $e_{i}$ is not $f_{j}$.