Minimum Spanning tree

Question

If a simple undirected graph with positive weighted edges has 10 vertices and 30 edges, such that the cost of the Minimum Spanning tree is 59. Now, if all the edges weights are increased by 2, then the cost of the new MST is

Comments

@joshi_nitish please tell the general formula

---

Got it

---

@Ashwani Kumar 2  Thank You 

Answer 1

Graph is simple undirected graph with positive weighted edges.

Now, Vertices(V)= 10, Edges(E)= 30 And cost of MST = 59

By definition of Tree: A tree is a simple connected graph with NO cycle.

If a tree has n vertices then there must be n-1 edges( it'll be similar for MST, after all its a tree).

 

Now, according to given question all the edges weights are increased by 2

Cost of New MST= given cost + weight increased by 2 only in 9 (n-1) edges                        || here, n= 10

                              =59 + (n-1)*2

therefore, Cost= 59+ 9*2 = 77