2.8k views
Let $G$ be a connected undirected graph of $100$ vertices and $300$ edges. The weight of a minimum spanning tree of $G$ is $500$. When the weight of each edge of $G$ is increased by five, the weight of a minimum spanning tree becomes ______.

edited | 2.8k views

First find no of edges in mst.
Mst has $n-1$ edges where $n$ is no of vertices. $100-1 =99$ edges
Each $99$ edges in mst increases by $5$ so weight in mst increased $99*5=495$
Now total weight of mst $=500+495=995$
by Active (5k points)
edited
+1
In question 300 edges given what does that statement say ? I didn't get it ?
+3
The total number of edges present in a graph is 300.

But as we know that the minimum number of edges required in a minimal connected single component graph is n-1.
No of edges =99 , now mention condition 99*5 = 495+500 = 995
by (91 points)
Since there are 100 vertices, there must be 99 edges in Minimum Spanning Tree (MST). When weight of every edge is increased by 5, the increment in weight of MST is = 99 * 5 = 495 So new weight of MST is 500 + 495 which is 995
by Loyal (9.7k points)