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

My approach

you just make cycle with 3 min weight edge

so in this you will get two edges weight 1,2.

now 3 is included in cycle so we cant consider it

so now remaining 4,5,6

so min is 4 becouse complete graph we consider

so ans is 1+2+4

Answer 2

Draw a complete graph of 4 vertices. Sort given edges y weight in increasing order. Just like Kruskal's algorithm sort the edges by weight. MST of graph with 4 vertices and 6 edges will have 3 edges. Now in any case we will have to include edges with weights 1 and 2 as they are minimum and Kruskal's algorithm includes minimum weight edge if it does not form a cycle. We can not have a cycle with 2 edges. In Kruskals algorithm, an edge will be rejected if it forms a cycle with the edges already selected. To increase the weight of our MST we will try to reject the edge with weight 3. This can be done by forming a cycle. The graph in pic1 shows this case. This implies, the total weight of this graph will be 1+2+4=7.

Answer 3

We would normally like to select the edges in the order — 1 then 2 then 3, getting the weight as 6.

But here, we have to maximize the weight. Go with Kruskal — it's human friendly.

We have to select 1 and 2. It is inevitable.

But now, instead of selecting 3, if we put 3 in a loop with 1 and 2, we won't have to take it. So, 3 is skipped.

Now, select 4.

Hence, $4+2+1=7$

Answer 4

Here 6 edges are given, just start applying Kruskal algo.  edge 1 is min it will be selected(no possibility of a cycle with just one edge). Now add edge 2(still no possibility of cycle since only two edges). These two edges will always be included

Now lets say we add edge 3 and it forms a cycle, so we would choose the next highest weight (i.e. edge 4). This MST will have weight 7. Now you can argue what if edge 4 forms a cycle with edge 1 and edge 2(the weight would now be 8, right???). No because if edge 4 forms cycle, edge 5 would not be include, edge 3 will be included since MST property show also hold.

Therefore we can go only till weight 7.