The cut property of MSTs states that, for any cut of the graph,
Athe heaviest crossing edge must be excluded from every MST
Bthe lightest crossing edge belongs to some MST
Cexactly half of the crossing edges belong to every MST
Dthe cut must be balanced (equal vertices on each side)
Answer & Solution
Correct answer: B. the lightest crossing edge belongs to some MST
Cut property: for any partition of the vertices into two non-empty groups, the least-weight edge that crosses the partition is safe to include in the MST. This is the greedy-choice property MST has; both Kruskal and Prim exploit it. The heaviest-edge / balanced-cut / 'exactly half' statements are not theorems.
Related questions
An NP-hard problem differs from an NP-complete one because NP-hard problemsThe first problem proved to be NP-complete wasA problem X is NP-complete if and only ifWhy does theoretical computer science draw the line at 'polynomial-time' for tractability?Which set inclusion is established (i.e., proven, not open)?The class NP is the set of decision problems for whichFloyd-Warshall detects the presence of a negative cycle byTopological sort is well-defined for