And I'm happy to report that we can indeed always do this.

So what I need to explain is the procedure by which we exhibit edge, this

edge E Prime, which doesn't get us into trouble after we swap, which still gives

us a spanning tree after the swap. So let me explain the procedure by which

we identify this magical edge E prime that we can swap with and still be a

spanning tree. So here's the way to think about it, so

we've got this spanning tree T star, we've got this edge which is not yet in T

star. Now, if we just plug E into T star, we're

going to get a cycle. Why?

Well, a spanning tree, remember, it has a path between each pair of vertices. So if

this new edge, maybe its endpoints are U and V. T star already has a path between

U and V, so when you plug in this new direct edge between U and V, it closes

the loop, it gives you a cycle. So let's go ahead and call that cycle

capital C. Let me also redraw the picture from the

example on the previous slide so you can see what that cycle was in that special

case. Now, here's the pattern to notice about

this cycle capital C, at least in this example, which is that the lousy edge,

the edge F, for which when we swapped, we didn't get a spanning tree, that's off of

this capital C. Whereas, the good edge, the edge where we could do a swap and get

a spanning tree, E prime that's on this same cycle capital C.

And that turns out to be true in general. So, when you add the edge to the spanning

tree and you get a new cycle, that cycle is what furnishes the candidates for

swaps that will give you a new spanning tree.

So the one lingering concern then, we have this cycle.

We would, all edges of the cycle are going to be good candidates for the

swapping. Wee just need to make sure that there is some edge that actually crosses

this cut A, B like the edge E prime does in the picture.

But here, we're going to rely on a fact from a previous video, the double

crossing lemma. Remember the double crossing lemma says,

that if you have a cycle that crosses a cut at least once, then it has to cross

it twice. All right.

So if it'd cross once, then it has to loop back around, then in looping back

around, it's going to cross it a second time.

So, in this cycle capital C, we know it crosses the cut A, B once,

that's because it includes the original cheapest edge across the cut E.

So, it's got to cross it a second time. There's got to be an E prime in the cycle

crossing the cut and that's going to allow us to do the swap and get a new,

cheaper spanning tree completing the contradiction.

So, just to spell things out in a little more detail.

So what we do is we first say we use the double crossing lemma.

So, we have this reported minimum spanning tree T star.

We have this cheap edge E knot in it. We plug E into the spanning tree, we get

cycle, we call the cycle capital C. The cycle crosses the cut A, B once,

through the edge E. It crosses it a second time by the double

crossing lemma. We're going to call that edge E prime.

Since E prime crosses the same cut as E, we know that E prime is strictly more

expensive than E. Remember we use the cheapest one crossing

this cut, A, B.

So now what we do is we execute the swap with this new edge E prime.

So E prime in T star. The cheapest edge, E, is not in T star so

we can swap them. We can take,

we can rip E prime out, we can stick E in.

Now something I want you to think through carefully at home, convince yourself this

is true, is that because we plucked E prime from the cycle, this new tree which

I'm going to call capital T, this is a spanning tree necessarily.

You know, intuitively, the reason being, you plug in E and you get this one cycle

involving E, and then when you rip out E prime, you destroy the cycle.

And because it's on a cycle, you don't destroy connectivity between any pair of

veriticies, there is still one path between each pair.

But make sure you believe that, convince yourself at home.

And once you're so convinced, you will also realize that we've finished a proof.

We've executed our proof by contradiction.

since E was the cheapest edge crossing the cut, and E prime is another edge

crossing the cut, E is got to be cheaper.

Since T differs from T star only in the swap of these two edges,

it's aggregated cost has gone down and that contradicts the purported optimality

of T star comp completing the proof of the cut property.