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

Many people here have not understood the question itself. Consider a complete graph of $4$ vertices. We have a total of $6$ edges of given weights but we do not have the exact graph. Many different graphs are possible each having a different structure. Consider these $2$ graphs, both of them are different. We do not know the exact structure of the graph, so what the question wants is to find the MST of all such structures and out of these tell the weight of the MST having maximum weight. The point about the MST of a graph with unique edge weights is valid for a given structure of the graph. With the same set of edge weights more than $1$ graph is possible and all of them can have different MSTs.

My solution: 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.$

Comments

nice answer with proper explanation.

---

we want maximum weight of mst then after taking 1 , 2 why are we not  taking 6 ??

plz help me

---

@prateek, Question is asking about maximum weight of minimum MST.

that's why we have to take care of weight should be as minimum as possible and along with maximum value.

---

okk i got now thanks

---

@Akash.dinker12 how can u specifically say that maximum weight should be 7?????

---

it is possible because first of all we want mst along with max.weight ,so we have to take edge weight 1 , 2 and after that we have no other choice so we have to take 4 edge weight that mst will be max weight which follow the property, we can't take any other edge that will not be mst then

---

if you really have understood the logic try to explain the logic writing 2 or 3 more lines so that a layman can also understand it , remembering what difficulties you faced while you were not getting the answer.. cause your answer to this question still did not clear the matter at all...im still in the same position where i was , after reading the previous answers...

---

Dude, images are broken. :(

---

why we are not using  1+2+5 = 8?

as it  also forms a spanning tree

and wht is the meaning of max possible weight in min. spanning tree .(MST)min spanning tree, is itself contains irreducible cost. HOW COULD BE IT MAXIMUM?

---

1,2,3 will be there in MST for the best case but In the question, we have to find-

The maximum possible weight that a minimum weight spanning tree of G can have

Step 1: Select 1,2 and 3 should be in the cycle if 3 is not in the cycle then it will be not our case.

Step 2: Now imagine 4,5,6 as maximum value set we can select 4 or 5 or 6 all are right but it is not asked ,we have asked the minimum value by selecting a maximum value as follows:-

$1+2+4 = 7 (\checkmark)$

$1+2+5 = 8 (\times)$

$1+2+6 = 9(\times)$

$1+3+4 = 8(\times)$

$1+3+5 = 9 (\times)$

$1+3+6 = 10(\times)$

$2+3+4 = 9(\times)$

$2+3+5 = 10 (\times)$

$2+3+6 = 11(\times)$

that is the reason 7 is the answer

---

Beautiful question.Beautiful answer

---

Kadak,
I was struggling to understand the answer of the question, but your explanation helped me a lot.. Thank you.

---

Consider these 22 graphs, both of them are different. We do not know the exact structure of the graph, so what the question wants is to find the MST of all such structures and out of these tell the weight of the MST having maximum weight.

In best answer which image to consider no image is given. Someone update the answer...

---

ASNR1010 

+1

---

@Arjun sir images are not visible which he is referring to… plz update this ans with an image 

---

where is image ? :|      @Lakshman Bhaiya the ans need an update the image is missing !!

Answer 2

Graph $G$ can be like this:

Comments

What we do if edges weight are

1,2,3,4,5,6,7,8,9 and 10.

than find maximum possible weight that a minimum weight spanning tree of G have..???

---

@Vikas123

then we have to include minimum 4 edges to make a spanning tree and we put edges 1 ,2 and 3 in a cycle. so 3 will be rejected.

=> 1 + 2 + 4 + 5 = 12

---

@Satbir

we can have edges 1 and 2, edge 3 makes cycle with 1-2, so take edge 4.
Now edge 5 makes cycle with 1-4 and similarly edge 6 makes cycle with 2-4, so now we can only take edge 7.

max MST weight= 1+2+4+7=14.

Answer 3

ans is 7.

it is said maximum weight pssbl.

draw a triangle. 3 sides weight 1 2 3. and 4th point is in center. join it with tringle vertices.. got more 3 sides. new side weight 4 5 6. now draw mst. take 1 take 2. cant take 3, so take 4. 1+2+4=7

Comments

U should hav drawn the image of ur answer ...

---

explain why...dont only state

---

@puja.See this...

Answer 4

Corrections or suggestions are welcomed.

Comments

as in 2,3 (we need to select smaller one so 2 has been selected)

NOTE:-just take all possible maximum and out of all possible maximum pick minimum

---

@tanaya.... perfect one..thanks... finally it is clear

---

The best answer for this question