Search code examples
graphhelperminimum-spanning-treeprims-algorithm

Minimum spanning tree of graph obtained by Prim's algorithm

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!!

Solution

  • 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.