Discussion
\(G = (V, E)\) is an undirected simple graph in which each edge has a distinct weight, and \(e\) is a particular edge of \(G\). Which of the following statements about the minimum spanning trees (MSTs) of \(G\) is/are TRUE?
I. If \(e\) is the lightest edge of some cycle in \(G\), then every MST of \(G\) includes \(e\)
II. If \(e\) is the heaviest edge of some cycle in \(G\), then every MST of \(G\) excludes \(e\)
Answer: B
Only statement II is true, so the answer is II only.
II is true (the cycle property): if \(e\) is the heaviest edge on some cycle, then in any spanning tree containing \(e\), removing \(e\) and adding another edge of that cycle reconnects the tree with smaller total weight. So no MST contains \(e\).
I is false. Being the lightest edge of some cycle does not force an edge into the MST. Take vertices A, B, C, D with edges AC = 1, BC = 2, AB = 3, AD = 4 and BD = 5. AB is the lightest edge of the cycle A-B-D (3, 4, 5), yet it is the heaviest edge of the triangle A-B-C, so by the cycle property no MST contains it; the MST is AC, BC, AD. So only II holds.
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