Prim's MST: Does the start node matter?

Question

I intuitively feel that if one is using Prim's algorithm to find a graph's minimum spanning tree, it doesn't matter which root node is picked - the resultant MST will have the same weight regardless. Is this correct?

Answer 1

That is correct. Choosing a different starting node could give you a different spanning tree, but it will always have the same weight: the minimal possible.

Answer 2

This is because of uniqueness of minima.

Proof:

Suppose there are 2 "different" minimum weights W1 and W2

W1 is minimum 
W2 is minimum
W1 != W2

This leads to contradiction because 
if W1 != W2 then 
   W1 < W2  -> W1 is minima
   or 
   W1 > W2  -> W2 is minima
Hence if W1 must equal W2.