unique minimum spanning tree sufficient and necessary conditions

Question

Given a graph G,which are the sufficient and necessary conditions , so that this graph has a unique minimum spanning tree?In addition , how can I proove these conditions?

So far , I had found that those conditions are :

1)For every partition of V(G) into two subsets, the minimum weight edge with one endpoint in each subset is unique.

2)The maximum-weight edge in any cycle of G is unique.

But I am not sure if this is correct.Even in case this is correct,I cannot prove its correctness.

Answer 1

This is false because at least the first condition is not necessary. The proof is by counterexample (source).

Take G to be any tree where all edge weights are 1. Then G has a unique MST (itself), but any partition with more than one edge crossing it has several minimum weight edges.

---

EDIT:

In response to your modified question...

There is a well-known sufficient (but not necessary) condition for the uniqueness of a MST:

If the weight of each edge in a connected graph is distinct, then the graph contains exactly one (unique) minimum spanning tree.

The proof is as follows (source):

For the sake of contradiction, suppose there are two different MSTs of G, say T1 and T2. Let e = v-w be the min weight edge of G that is in one of T1 or T2, but not both. Let's suppose e is in T1. Adding e to T2 creates a cycle C. There is at least one edge, say f, in C that is not in T1 (otherwise T1 would be cyclic). By our choice of e, w(e) ≤ w(f). Since all of the edge weights are distinct, w(e) < w(f). Now, replacing f with e in T2 yields a new spanning tree with weight less than that of T2 (contradicting the minimality of T2).

However, regarding "sufficient and necessary" conditions for the uniqueness of a MST, I do not believe any are known to exist.

Answer 2

Actually, there is a necessary and sufficient condition for unique MST. In the book A First Course In Graph Theory, it is given as an exercise:

Exercise 4.30

Let G be a connected weighted graph and T a minimal spanning tree of G. Show that T is a unique minimal spanning tree of G if and only if the weight of each edge e of G that is not in T exceeds the weight of every other edge on the cycle in T+e.

I write my proof here.