GATE CSE 2001 | Question: 15

Question

Consider a weighted undirected graph with vertex set $V = \{n1, n2, n3, n4, n5, n6 \}$ and edge set $E = \{(n1,n2,2), (n1,n3,8), (n1,n6,3), (n2,n4,4), (n2,n5,12), (n3,n4,7), (n4,n5,9), (n4,n6,4)\}$.

The third value in each tuple represents the weight of the edge specified in the tuple.

• A. List the edges of a minimum spanning tree of the graph.
• B. How many distinct minimum spanning trees does this graph have?
• C. Is the minimum among the edge weights of a minimum spanning tree unique over all possible minimum spanning trees of a graph?
• D. Is the maximum among the edge weights of a minimum spanning tree unique over all possible minimum spanning tree of a graph?

Comments

Is the minimum among the edge weights of a minimum spanning tree unique over all possible minimum spanning trees of a graph?

Does this talk about any MST of any graph possible?

In that case, shouldn't this MST make the given statement false? Please help :(

Same can be argued for Option D.

---

I have the same question.
People here have answered C and D specific to this question, but the phrasing of the question seemed like it was meant for all possible graphs.

---

For Option C , D meaning ( Solve Using Krushkal)

Option C: Minimum Edge Weight

This asks if every MST of a given graph will have the same "cheapest" edge.

Meaning: If you find two different MSTs, $T_1$ and $T_2$, is the weight of the smallest edge in $T_1$ equal to the weight of the smallest edge in $T_2$?

The Rule: Yes. The multiset of edge weights is identical for all MSTs of a graph. If you sort the edge weights of any MST from smallest to largest, the list will be exactly the same every time.

Option D: Maximum Edge Weight

This asks if every MST will have the same "most expensive" edge.

Meaning: Does the maximum weight used to connect the graph in $T_1$ have to match the maximum weight used in $T_2$?

The Rule: Yes, for the same reason mentioned above. While the specific edge might change, the value of that maximum weight is fixed across all MSTs for that specific graph.

Answer 1

• A. Edges with weights: $2,3,4,7,9$

$\text{Minimum Spanning Tree}$

• A. Number of distinct minimum spanning tree: $2 (2^{\text{nd}}$ with a different edge of weight $4)$
• B. Yes
• C. Yes 

Comments

Can any one tell me the meaning of option c n d @jayendra

---

@srahulda

Minimum and maximum edge weights are unique(min=2 and max=9) in the 2 possible MSTs. (we don't have more than 1 minimum/maximum edges)

---

Take one MST and find the smallest edge weight in it.
Take another MST and find its smallest edge weight
Do this for all MSTs and see that does every MST have the same minimum-weight edge value?
for statement C answer is yes 
and it is 2 that is in every MST possible from given.

Does every MST have the same maximum-weight edge value?
similarly for statement D
we find maximum egde that in every MST which is edge weight 9 

 

Answer 2

Minimum spanning tree:

Comments

Please add this image in your first answer. It will make answer more elegant.

Answer 3

The number of vertices in the graph is 6. So the number of edges in the MST will be 5.

A) {(n1,n2,2),(n1,n6,3),(n2,n4,4),(n3,n4,7),(n4,n5,9)} and {(n1,n2,2),(n1,n6,3),(n3,n4,7),(n4,n5,9),(n4,n6,4)}

B) Number of distinct minimum spanning trees is 2.

C) Yes. It’s 2.

D) Yes. It’s 9.

-------------------------------------------------------------------------------------------------------------------------------------------------------------------

Assumption:

C)Is the minimum among the edge weights of a minimum spanning tree unique over all possible minimum spanning trees of the graph?

If we consider the gate question to be correct: options C and  D will be False. Because of duplicate edge weights.