The Gateway to Computer Science Excellence

+7 votes

Yes I think the claim is true as

If Edge weights are not distinct then we can have multiple Spanning trees

Suppose Consider an example

here we choose edges with weight 1 then with 2 then with 3

In case of 3 if we consider both edges whose weight is 3 the a cycle is formed so we consider only 1 edge by this we can have 2 Spanning trees with same weights

Spanning tree 1 :

Spanning Tree 2:

Let me know if I'm wrong

0 votes

Yes, I agree with the claim made and for its proof,

Taking an instance where we have more than one similar edge weights could be the graph (not neccessarily) on which applying kruskal's algo could give us more than one M.S.T's .

NOTE:- The claim holds false everytime we have distinct edge weights.

Let me know if I was wrong.

Taking an instance where we have more than one similar edge weights could be the graph (not neccessarily) on which applying kruskal's algo could give us more than one M.S.T's .

NOTE:- The claim holds false everytime we have distinct edge weights.

Let me know if I was wrong.

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.3k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.1k
- Non GATE 1.5k
- Others 1.5k
- Admissions 595
- Exam Queries 576
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 17

50,645 questions

56,554 answers

195,706 comments

101,561 users