Yes 4 is not always true consider a triangle. all edges form cyclem

The Gateway to Computer Science Excellence

+1 vote

+1

and i think statement 3 is true as all the edges will be distinct when the first best MST is formed second best MST is formed by removing a edge with the next highest edge so the second best also will be unique

correct me if i'm wrong!!

correct me if i'm wrong!!

0

@Akriti, even i marked same(C). but see option (4) it says edges that do not lie in any cycle must be in MST, it doesn't say what if they lie in cycle. So (4) is true.

And for (3) who knows maybe someone can draw a graph. But not sure. maybe it depends on how weights are distributed (1+4) = (3+2)

And for (3) who knows maybe someone can draw a graph. But not sure. maybe it depends on how weights are distributed (1+4) = (3+2)

0

3rd sttement says that MST will include all edges not in cycle,it also means that we can include any edge not in ycle even if it is the maximum size edge,but thats not true..right??

anmd since,weights are unique,so second best will just not contain the minimum weight edge,rest all same.can u give nay counter example for 3rd??

anmd since,weights are unique,so second best will just not contain the minimum weight edge,rest all same.can u give nay counter example for 3rd??

0

no even if a max weight edge is not in cycle it is to be included, consider graph::

AC = 100,DC = 101,CB = CE = BE = 1

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

50,737 questions

57,280 answers

198,174 comments

104,840 users