GATE CSE 2015 Set 3 | Question: 40

Question

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

Comments

gate pyq on same topic 

https://gateoverflow.in/39673/gate-cse-2016-set-1-question-14

---

Here $300$ edges in $G$ this information has no use for soln.
Only use $100$ vertices and the given weight of MST $500$, weight increase of $5$

---

 Try to solve by just taking small graph

 

Answer 1

To connect 100 vertex we need 99 edges.
as previously the MST has weight as 500.
Now that 500 +  (99 * 5 ) = 995 in total

so Final wight of MST is 995.

Comments

gate pyq on same topic 

https://gateoverflow.in/39673/gate-cse-2016-set-1-question-14