3,036 views

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.

1. List the edges of a minimum spanning tree of the graph.
2. How many distinct minimum spanning trees does this graph have?
3. Is the minimum among the edge weights of a minimum spanning tree unique over all possible minimum spanning trees of a graph?
4. Is the maximum among the edge weights of a minimum spanning tree unique over all possible minimum spanning tree of a graph?

### 1 comment

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?

Same can be argued for Option D.

### Subscribe to GO Classes for GATE CSE 2022

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

1. Number of distinct minimum spanning tree: $2 (2^{\text{nd}}$ with a different edge of weight $4)$
2. Yes
3. Yes
by

Although question is simple but it will be good if you can add some explanation for other options for justification.

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

What does "minimum" mean here? Does it mean a "value" or a specific edge with the minimum value?

@jayendra, hi sir, how is the answer for c) and d) yes? for c), the minimum weight edge is 2 which is present in both the spanning tree's, so it's not unique. for d), the maximum weight edge is 9 which is also present in both the spanning tree's, so it's also not unique. According to this, answer should be no for c) and d). Am i missing something here, please reply.

What I think is, in this complex statement. Both options C and D are Correct(YES).

OPTION C: YES

1. Construct a particular MST.
2. make a set of all weights in MST i.e. {2,3,4,7,9}
3. min wt=2, has occurred only once in this set i.e. unique(This is what they are asking).
4. repeat above over all MSTs.(i.e. min wt=2 is unique in all MSTs).

(I dont think that they are comparing between two diff sets/MSTs).

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

@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)

Minimum spanning tree:

by

### 1 comment

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.