The Key Question
Prim’s algorithm makes a local decision at every step: it chooses the lightest edge that connects the current tree to a vertex outside the tree.
But why is this safe? Why does choosing the cheapest available edge now still lead to a globally minimum spanning tree later?
The answer comes from one of the most important ideas behind minimum spanning tree algorithms: the cut property.
What is a cut?
A cut separates the vertices of a graph into two groups.
In Prim’s algorithm, one side of the cut is the set of vertices already inside the growing tree. The other side contains the vertices still outside the tree.
Any edge that connects these two groups is called a crossing edge.
Visual Intuition — The Frontier
Think of Prim’s current tree as an island. The crossing edges are bridges from that island to the rest of the graph.
Prim always chooses the cheapest bridge that expands the island.
The Cut Property
The cut property says that if we split the graph into two groups, then the lightest edge crossing that split is safe to include in some minimum spanning tree.
Prim uses this property at every step. The current tree defines one side of the cut, and all remaining vertices define the other side.
So when Prim chooses the lightest edge crossing that cut, it is making a safe greedy choice.
Why no cycle is created?
Prim only adds edges that connect the current tree to a vertex outside it.
Since the new vertex was not already in the tree, there was no previous path from the tree to that vertex inside the tree.
Therefore, adding this edge cannot create a cycle.
Why the result spans all vertices?
Each step adds exactly one new vertex to the tree.
Starting from one vertex, Prim keeps expanding until there are no vertices left outside.
In a connected graph, there is always at least one edge from the current tree to the outside until every vertex has been included.
Why the result is minimum?
At every step, Prim adds an edge that is safe according to the cut property.
This means each chosen edge can belong to some minimum spanning tree. Repeating this safe choice step by step preserves the possibility of reaching an optimal final tree.
When all vertices have been included, the algorithm has built a spanning tree made only of safe choices.
Key Insight from Part 3
Prim works because each greedy choice is protected by the cut property.
The algorithm does not choose a cheap edge randomly. It chooses the cheapest edge that crosses from the current tree to the outside.
That is why Prim can grow a tree locally while still guaranteeing a globally optimal result.