Alright. 
So now that we've completed our warm up 
by showing that at the very least, Prim's 
algorithm outputs a spanning tree. Let's 
move on and actually show it outputs a 
minimum cost spanning tree. 
And to prove this theorem, we're going to 
have to tackle head-on the kind of crisis 
which you always face when designing a 
greedy algorithm. 
So in a greedy algorithm, you're making 
an irrevocable decision, 
like in Prim's algorithm, we're including 
an edge in our tree and never revisiting 
it later. 
And, how can you be sure that you're not 
making a mistake? 
How can you have a guarantee that the 
decision you're making seemingly 
myopically right now is actually a good 
decision won't come back to bite you 
later? 
So it turns out for minimum spanning 
trees, there is a beautiful condition 
which tells you when you're guaranteed to 
not regret including an edge into a 
spanning tree, 
but guarantees when an edge has to belong 
to the minimum spanning tree. 
So that's called the cut property, 
it's the subject of the next slide. 
So this is a cool enough property that 
we're going to bestow it not just with 
all caps but even with a box. 
Now, that's a pretty good property. 
So what does it states? 
Well, consider an edge of a graph, an 
edge that we are wondering if it's safe 
to include it in the tree so far. 
So here is this sufficient condition 
guaranteeing that you won't regret 
including this edge in the tree so far. 
The condition is stated in terms of the 
cut. 
So suppose you can find a cut, A, B with 
the property that amongst all edges in 
the graph G, that happened across this 
cut, the edge E is the cheapest edge 
crossing this cut. 
Okay? So not only should edge E cross 
this cut, A, B, but it should cheapest 
such edge. 
If this condition is met, then we 
definitely want them include the edge E 
in our solution. 
Indeed, the edge E has to be a member of 
any minimum spanning tree of the graph. 
So in this video, we're going to assume 
that the cut property is true. 
It is by no means obvious. 
It definitely requires a proof. 
I'll give you the proof in a separate 
video. 
It's not, 
it's a little bit tricky. 
It's based on a subtle exchange argument. 
For this video, we're going to assume 
that it's true, however, and we just want 
to be quiet, so that we want to figure 
out what it's good for. 
Now, I will soon show you that it 
actually implies correctness of Prim's 
algorithm. 
But just to get a feel for it, let's look 
at a much simpler graph. 
Let's just look at a four cycle. 
Four nodes, four edges with edge costs 1, 
2, 3, and 4. 
So let's look at, let's look at a few 
cuts. 
So, let's look at the cut. 
We're on one side of the cut, 
I put the upper right vertex, 
and on the other side of the cut, I put 
the other three vertices. 
So there are two edges crossing this cut, 
the edge that has cost 1, the edge that 
has cost 2. 
So the edge with cost 1 is the cheapest 
edge crossing this cut, so by the cut 
property, the edge of cost 1 has to be in 
the MST. 
Okay. 
So we looked at one cut and both the cut 
property [INAUDIBLE} to stick in the MST. 
That was pretty cool. 
let's look another cut. 
Let's look at a cut where on one side, we 
just put the bottom right vertex, 
and on the other side, we put all Now 
this cut has two edges crossing it the 
edges that have cost 2 and cost 3. 
The edge of cost 2 is the cheapest edge 
crossing this cut. 
So by the cut property, it has to be in 
the MST. 
So that's cool. 
So we know the two has got to be there. 
Now let me point out something 
interesting that's happened, 
which is that, it is not the case that 
this edge of cost 2 is the cheapest 
crossing, every single cut that it 
crosses. Remember when we looked at cut 
number 1, this edge of cost 2 was 
actually the most expensive edge crossing 
that cut. But, we found a different cut 
that is the cheapest crossing and that's 
enough to justify the cut property. 
So in other words, 
all that's important for the cut 
property, 
I just got to find you one cut for which 
an edge is the cheapest, that's enough to 
conclude its presence in the MST. 
So similarly, we can look at a third cut 
just consisting of the bottom left 
vertext and the other three vertices. 
And it's the same story, there are two 
edges crossing this cut, the edge of cost 
3, the edge of cost 4. 
The edge of cost 3 is the cheapest edge 
crossing this cut, so we know it's got to 
be in the MST. 
And again, when we look at cut number 2, 
it didn't tell us whether or not the edge 
of cost 3 is in the MST, but when we 
looked at cut number 3, that was enough 
to conclude that the edge of cost 3 has 
to be in the MST. So there we go. 
So we could use the cut property that 
construct an entire MST. 
On the other hand, there's no way to use 
the cut property to try to justify the 
edge of cost 4. 
Any cut that you pick for which the edge 
of cost 4 crosses, there will be some 
other cheaper edge crossing it. 
So you can never use the cut property as 
one would hope to justify the inclusion 
of the edge of cost 4 and you'd better 
not be able to, because 4 is not in the 
MST. 
Now a quick side note, some of you might 
be wondering when I wrote in the 
conclusion of the cut property, 
I said the MST of G, so that would seem 
to indicate that the minimum spanning 
tree is unique. 
So that deserves a quick comment. 
so first of all, if the edge costs are 
not distinct, if you have ties between 
edges, then you can certainly have 
multiple different minimum spanning trees 
and you have to state the cut property a 
little bit differently. 
But again, in the lectures we are just 
going to assume distinct edge costs, so 
that's not a problem. 
And in fact, something that will be a 
consequence of the next slide, we'll 
notice that the minimum spanning tree is 
unique with distinct edge cost. 
It's not obvious, but we'll prove it 
shortly. 
All right. 
So what I want to do to finish up this 
video is I want to assume that the cut 
property is true. 
And then, from that, I want to derive, I 
want to argue that Prim's algorithm is 
correct, 
always outputs an MST. 
The proof of the cut property is 
non-trivial and deserves its own video, 
which you can see separately. 
All right. So given the tools that we've 
developed, this argument is actually 
going to be quite short. So let's assume 
that the cut property is a true statement 
and let's begin by building on the 
previous video. 
The previous video argued that Prim's 
algorithm outputs a spanning tree, didn't 
argue it was a minimum one, but it argued 
it's a spanning tree, it spans all the 
vertices and has no cycles. 
Let's call the output of Prim's algorithm 
at the end of algorithm T star. 
Now, 
stare at the cut property, 
stare at the pseudocode of Prim's 
algorithm. 
What happens in each iteration of Prim's 
algorithm? 
Well, we have our set capital X, that's 
what we spanned so far. 
There's the rest of this stuff, V - X, so 
that's a cut X, V - X. 
What does Prim choose to include next? 
Well, in brute-force searches through the 
edges, the cross is cut and it adds the 
cheapest one of them. 
Well, that is right in the wheelhouse of 
the cut property. 
What does the cut property says? It says 
cheapest edges crossing cuts have to be 
in the MST. 
So they just fit together beautifully. 
Prim's algorithm explicitly picks an edge 
at each iteration which satisfies the 
hypothesis of the cut property and 
therefore has to be in the MST. 
So remember, the conclusion of the cut 
property says edges so justified must 
belong to the MST. So if everything in T 
star is justified by the cut property, 
then everything in T star is in the MST 
so T star is a subset of the MST. 
But T star, of course, as we have argued, 
is already a spanning tree in it of 
itself. 
And, if you add more edges to T star, 
it's no longer going to be a spanning 
tree, because you are going to pick up 
cycles, right? If you ever have something 
that is connected, there is a path from 
each pair of vertices, and you add a new 
edge, you are going to close a path, 
you're going to get a loop. 
Okay? 
So T star is already a spanning tree, and 
you can't have anything bigger and still 
be a spanning tree. 
So therefore, this has to be the minimum 
spanning tree, 
there cannot be anything else. 
So for this reason, T star must in fact 
be the minimum cost spanning tree of the 
graph. 
Since the input graph was arbitrary, 
assuming only it was connected, this 
completes, assuming the cut property, the 
proof of correctness of Prim's minimum 
spanning tree algortihm.