GATE CSE 2016 Set 1 | Question: 39

Question

Let $G$ be a complete undirected graph on $4$ vertices, having $6$ edges with weights being $1, 2, 3,  4, 5,$ and $6$. The maximum possible weight that a minimum weight spanning tree of $G$ can have is __________

Comments

It is not at all rocket science: Here is the solution

You pick up four min edges to get MST so you pick edge with weight 1 then 2 as no choice but when picking up 3 you can ask can I avoid this one so that I can pick 4 or above which has greater weight and answer is yes you simply make weight 3 edge as so that cycle is formed, and now will have to pick edge with weight 4 as you have no choice and no additional cycle can be formed as graph is complete 4

---

@arjun sir graph is complete that is all distinct vertices are connected with unique edge so only one graph structure is possible ?
Square shape with diagonal vertices connected
No of edges = 4*(4-1)/2 = 6 edges as given in graph

---

I think there are only 2 mst possible with min weight 6,7 so answer will be 7

this question gets to many view just due to  wrong interpretaion of question i.e. what actually asking in question is confusing means should we apply mst algo or not like this confusion .

Answer 1

The question is asked such a way that you have make the weight maximum in a MST.No matter how you draw the graph you can't make the weight more that 7,It may be 6 or 7 but they asked about maximum possible weight that the MST have.So 7 is the maximum, You can' make it more than that because that will not be MST.

Comments

How can we prove that weight will not more than 7

Answer 2

This question ask as how many possible way of drawing the above as to find MST in which maximum possible weight, so in which we can draw only in two ways. in first way MST is 1+2+3=6 and other 1+2+4=7 no other ways can draw. so max possible weight that MST is 7.

Answer 3

As other have explained with diagrams, the correct answer is 7. The explanation is as follows:

Keep in mind the Kruskal's algorithm for generating MST of a graph. It will pick edges in increasing order, and include them in MST if it does not form a cycle. So it will first pick edge of weight 1, then edge of weight 2 (2 edges cannot form a cycle). Now it will pick edge of weight 3 if it does not form a cycle, but since we want to maximize the weight, we will label edges of a triangle(cycle) with edge weights 1,2,3 respectively so that we cannot pick edge with weight 3 in our MST because it will then form a cycle. Therefore we have a configuration where the MST has 3 edges with weight - 1,2,4 and hence total weight = 7

Answer 4

The minimum spanning tree for a distinct edge weighted graph is unique .

And as the minimum spanning tree is unique the only possible weight is 6 ( selecting the lowest possible weights 1,2,3 ) 

Comments

In this situation ans can not be (1+2+3) = 6