In minimum spanning trees, the cut property is used to justify Prim's…
2025
In minimum spanning trees, the cut property is used to justify Prim's algorithm. What does the cut property state?
- A.
A maximum-weight edge in the graph must be part of every MST.
- B.
A minimum-weight edge in the graph is the only edge Prim's algorithm can choose.
- C.
A minimum-weight edge crossing the current cut is safe to add to an MST.
- D.
A maximum-weight edge crossing a cut is safe to add to an MST.
Attempted by 150 students.
Show answer & explanation
Correct answer: C
CONCEPT
A cut partitions the vertices of a connected, weighted, undirected graph into two non-empty sets. A crossing edge has one endpoint on each side of that partition.
The cut property says that a lightest edge crossing a cut is safe for the minimum spanning tree: it can be included in some MST. When all edge weights are distinct, that crossing edge is forced into the MST.
APPLICATION
In Prim's algorithm, the vertices already in the growing tree form one side of a cut, and the remaining vertices form the other side.
The candidate edges are the edges crossing that current cut.
Choosing a minimum-weight crossing edge is safe, so adding it preserves the possibility of completing a minimum spanning tree.
Therefore, the cut-property statement that fits Prim's algorithm is: a minimum-weight edge crossing the current cut is safe to add to an MST.
CONTRAST
A maximum-weight edge rule can add unnecessary cost and is not justified by the MST cut property.
A globally minimum-edge rule misses the cut restriction used in Prim's step-by-step growth.
A maximum-weight crossing-edge rule keeps the cut setting but reverses the light-edge condition.
RESULT
The answer is: a minimum-weight edge crossing the current cut is safe to add to an MST.