Cut Property

  • A cut is an assignment of a graph’s nodes to two non-empty sets.
  • A crossing edge is an edge which connects a node from one set to a node from the other set.
  • Cut property: Given any cut, minimum weight crossing edge is in the MST.
    • For rest of today, we’ll assume edge weights are unique.