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 ANSWER FOR THIS QUESTION IS  6 !!

sorry for the disappointment!!

now the minimum spanning tree for a graph with distinct edge weights is UNIQUE if u want reference  ( https://en.wikipedia.org/wiki/Minimum_spanning_tree)

now the given graph is having distinct edge weights so minimum spanning tree will be unique and its always 6

the question about maximum ???

there is no concept of max or min in minimum spanning tree !!!

Comments

Its true that the minimum spanning tree for a particular graph with distinct edge weights is unique, but here we have to assign the edge weights to the edges,so we are changing the graph such that we get the maximum weighted minimum spanning tree among all the unique minimum spanning trees of the different graphs possible.

Answer 2

Given graph will be having 6 or 7 as the weight of its MST.
We will get weight 6 when there will be no cycle formation during picking of edges weight 1,2,3 and thus 1+2+3 = 6.
But in the worst case, we will be having cycle formation when we pick edge having weight 3 and thus, in that case, we'll have to leave weight 3 and pick edge with weight 4 (always).So this will give weight 1+2+4 = 7.
Since we are having two variants of MST having weight 6 and 7, we have to choose maximum among them.
So the answer is 7.

Answer 3

GRAPH CAN BE LIKE THIS ALSO USING CUT Property of MST 

MST with maximum weight 7

Answer 4

This question deals with orientation of complete graph

Now we have 2 options

1) we place edges  having wt 1, 2 at digonals

2) or on sides

Because any way those edges are part of spanning tree

Iin the first case it is not possible to construct a mst neglecting edge with wt 3

But in second case we can make mst with neglecting 3 by placing such that it forms cyle