GATE CSE 2018 | Question: 47

Question

Consider the following undirected graph $G$:

Choose a value for $x$ that will maximize the number of minimum weight spanning trees (MWSTs) of $G$. The number of MWSTs of $G$ for this value of $x$ is ____.

Comments

kruskal or prime which should take?

---

We can use Kruskal algo.i.e. keep selecting min weight edges and if a cycle occurs then ignore that edge. Do this until you select $n-1$ edges.

$\therefore$ $4$ is correct.

---

Value of $x = 5$
$\therefore 4 \;\text{MWSTs}$ possible.

Answer 1

Number of possible MSTs increase, when we have multiple edges with same edge weights.

To maximize the number of MST, $x$ should be $5.$
In the question, number of MST is asked for the value of $X$.

So, number of MST $= 2\times 2 = 4$  (Answer)
$($Because one $4$ forms cycle, cant be included in any way. Now from two $4$ and $5$ we can select one in $2\times 2 = 4$ ways$)$

Comments

@ASNR1010 yes

---

@ASNR1010 for x = 1,2,3,4 we will get 2 MST’s.

---

why not x=3?

Answer 2

Some definitions :

Cycle property: If edge e is the heaviest edge of some cycle in graph G then this edge is not included in ANY mst of G.

Cut Property : For any cut (S,V-S) of graph G=(V,E), if edge e is the lightest of all edges crossing the cut (crossing the cut means having one endpoint in S and other in V-S) then edge e is safe for being added to MST and this edge e is included in any MST of G.

By cycle property of MST, it is clear that the edge CD won't be included in any MST.

Now our remaining graph that we need to analyze is

Now it's clear that edges AC(wt-1) and AD(wt-3) would surely be in included in any MST(light edges crossing the cut).

Case 1: Suppose x is 1

Now edges AC, AD, AE would be any MST and since now only one vertex would remain to be connected to this MST, vertex B can be connected via AB or BC.

Hence, in this case only 2 MST.

Case 2: X is 3

Similar to case 1, edges AC,AD,AE would be in any MST of G, and now B need to connected.Here also, 2 MST possible.

Case 3: X is 4.

Here, edges AC, AD would be in ANY MST.Now, since DE becomes the heaviest edge of the cycle, by cycle property this edge won't be included in any MST of G. So, I considered in the above diagram edge DE to be removed.

Now to connect to vertex E, only edge is AE so it will be present in ANY MST.

Now vertex B need to be connected to the MST formed,and here also we will have 2 choices,either take AB or take BC.

2 MST possible in total.

Case 4: X is 5.

From above, it is clear that AC and AD would be included in any MST of G by cut property.

Now to connect vertex E to MST formed, we have two choices either take DE or AE.

And to connect vertex B, 2 choices, AB or BC.

In total 2*2=4 MST possible.

Case 5: X is >5 say 6.

The situation in this case would be that AE being heaviest edge of cycle, would be excluded from all MST and below can be imagined,

Edges painted in green would always be in any MST of G.

And edge DE being pendant edge will also be in any MST of G.

So only choice is created for vertex B to be connected via 2 edges.

So, total 2 MST in this case.

Final Answer- Total 4 MST possible.

Comments

@Ayush Upadhyaya Sir, Wonderful Explanation !!!!!!

Answer 3

Ans: 4

Comments

@ Prashant Kumar 4 Good explanation, but why we particularly take x=5? 

---

Think opposite, What if you choose x to be 3 or 4 they will form only one unique M.S.T in that cycle. To maximize no. of M.S.T  we have to choose values in a cycle such that the value is always duplicate so the potential candidate for the value of x will be the largest weighted edge that is already in the cycle.

---

Makes sense, thank you! :)

Answer 4

In question they have asked about max no of min spanning tree

There was a cyclic with contain two edge of same magnitude and min in cyclic so two min spanning tree

Now when we take x=5 it will have 2 possibly

So total min spanning tree=2*2=4