Generic minimum spanning tree

Question

I am reading myself about Minimum Spanning trees in Cormen,etc. Following is the generic minimum spanning tree.

Assume we have a connected, undirected graph G = (V, E) witha a weight function w:E->R and we wish to find a minimum spanning tree for G. Here we use greedy approach. This greedy strategy is captured by the following "generic" algorithm, which grows the minimum spanning tree one edge at a time. The algorithm manages a set of edges A, maintaining the following loop invariant.

Prior to each iteration, A is subset of some minimum spanning tree.

GENERIC-MST(G,w) 
A = NULL
while A is not a spanning tree 
  do find an edge (u, v) that is safe for A 
  A = A ∪ {(u, v)}
end while

return A

Questions

1. What does authore mean in invariant that "A" is subset of some minimum spanning tree? What is "some" in this statement? i taught there is only one MST.

2. In above pseudocode what does author mean by "A is not a spanning tree"? i.e., how and when while loop exits?

3. In pseudo code where "some" minimum spanning tree, here my understading is only one. am i right?

Can any one pls explain with small example?

Thanks!

Answer 1

1. Absolutely not. MST are not necessarily unique. For example:

All edges are of equal weight.

u --- v
|     |
|     |
w --- x

The above graph has 4 MSTs, by removing any edge.

2. A spanning tree T = (V,e) in G = (V,E) is such that |e| = |V|-1

3. No.