Course contentsShow
← Computer Science
Lesson 1013 of 2,87224. Minimum Spanning Trees and Network FlowFree lesson

Cut Property and MST Correctness

Learn the cut property theorem that forms the foundation for proving MST algorithm correctness.

Cut Property and MST Correctness

What You'll Learn

You'll learn the cut property theorem, the fundamental principle that proves why greedy MST algorithms actually find the minimum spanning tree.

The Core Idea

When building a minimum spanning tree, you need confidence that choosing certain edges is guaranteed to be safe. The cut property provides that guarantee.

Understanding Cuts

A cut of a graph is simply a partition of vertices into two disjoint sets. Imagine drawing a line through your graph that divides all nodes into two groups. Any edge connecting a node from one group to a node in the other is called a crossing edge.

The Cut Property Theorem

If you have a cut with no MST edges crossing it yet, then the minimum-weight crossing edge is safe to add to your MST.

Think of it like this: Imagine building bridges between two islands (the two sides of the cut). If you haven't connected them yet with any "approved" bridge, the lightest available bridge must be part of the optimal solution. Why? Any other spanning tree would either not connect the islands (invalid) or use a heavier bridge (suboptimal).

Why This Matters

The cut property is the theoretical foundation for algorithms like Kruskal's and Prim's. Every time these algorithms select an edge, they're implicitly using the cut property to guarantee correctness:

  • Kruskal's: Each new edge connects two separate tree components (a natural cut)
  • Prim's: Each edge crosses from the growing tree to unexplored vertices (another cut)

Without the cut property, we'd just be guessing that greedy choices work—with it, we have mathematical proof.

Key Takeaway: The cut property guarantees that choosing the lightest edge crossing any cut without MST edges is always safe, forming the correctness proof for all greedy MST algorithms.