Minimum spanning tree of graph obtained by Prim's algorithm

Question

I need some assistance on a Prim's algorithm problem:

Let T be a minimum spanning tree of graph G obtained by Prim's algorithm. Let Gnew be a graph obtained by adding to G a new vertex and some edges with weights, connecting the new vertex to some vertices in G. Can we construct a minimum spanning tree of Gnew by adding one of the new edges to T? If you answer yes, explain how; if no, explain why.

Thank you in advance!!

Answer 1

Can we construct a minimum spanning tree of Gnew by adding one of the new edges to T?

No. Not in general. Assume T has been generated by considering verteices in order v1,v2,...,vn-1

Let vn be the new vertex and (v1,vn) be a weighted edge (v1 is the root of T), if the weight of (v1,vn) is smaller than the weight of (v1,v2) in T, this would not be MST anymore.

Answer 2

No, this might be easier to visualize with a counter example:

as seen from above, not only is the new MST missing an edge compared to the original MST. It also uses both vertices instead of just one.

Answer 3

not in all cases we can add new edge in T , it depends on the weight of new edges, because sometimes the old MST(T) will changes if the new edges weight is small than other weight in graph