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

The mid section consist of 1 and 3 and will always be included in spanning tree. Left section has 2 choices and in right section if we make x=5, then in right also we have 2 choices. Hence total possible spanning trees are 2*2= 4 for x=5