Discussion
Consider an undirected graph G with vertices {A, B, C, D}. In graph G, every edge has distinct weight. Edge CD has minimum weight. Edge AB has maximum weight. Then, which of the following is false ?
Answer: C
The false statement is no minimum spanning tree contains AB.
AB is the heaviest edge, but if it is the only edge connecting part of the graph (a bridge), every spanning tree, including the minimum one, must contain it. So the claim cannot be guaranteed.
The other statements are true. With distinct weights the MST is unique. The lightest edge, CD, is always in the MST. And by the cycle property the heaviest edge on any cycle is excluded, so if AB is in the MST it lies on no cycle, meaning its removal disconnects G.
Post your comment
Please log in or register to post a comment.
Examination Categories
- SSC Exams
- Banking Exams
- Teaching Exams
- Civil Services Exams
- Railways Exams
- Engineering Recruitment Exams
- Defence Exams
- State Government Exams
- Police Exams
- Insurance Exams
- Nursing Exams
- Other Government Exams
- NRA CET
- PG Entrance Exams
- Campus Placement
- MBA Entrance Exams
- CUET and UG Entrance
- Judiciary Exams
- Regulatory Body Exams
- Software Development