A Spanning Tree of a graph G is a subgraph of G which

is a tree and spans all the vertices of G. And then,

Minimum Spanning Tree is a spanning tree of the smallest weight.

Here's an example, that's exactly what we did in the road repair problem.

This is a tree which spans the whole graph and has a minimum weight.

We want to solve this problem each time when we want to connect cities,

computers, or satellites in a network in an optimal way.

This program has lots

of real life applications and this

is why we know many efficient algorithms for this program.

And we will see one called,

Kruskal's Algorithm, actually, we already solved it.

This is how it works,

it starts off with an empty graph and then,

n minus 1 times adds an edge which doesn't add any cycle and has the smallest weight.

That's exactly what we did in the road repair problem.

Let me show it to you.

First, I add the smallest edge

which has weight one, then I add the smallest edge which now has weight two.

Now I can't add this edge of weight three because it adds a cycle.

So I don't add this edge,

but I add the other edge of weight three because it doesn't add, create any cycle.

Now I can add this edge of weight three which doesn't create any cycles, but I don't

this edge of weight four because it does create a cycle.

So I keep doing this.

This edge doesn't create any cycles,

it just has two connected components in orange, but no cycles.

And finally, I add this edge,

I added n-minus 1 edges,

I have it connected the graph of three which spans the whole graph.

This algorithm is called Kruskal's Algorithm and actually

it finds a minimum Spanning Tree. Let's prove it.

We'll show that at every step of our algorithm

the currently added edges belong to some Minimum Spanning Tree.

If it proves the statement,

then it also means that at the very last step when we have n-minus one edges,

this is also a subgraph of some Minimum Spanning Tree.

But since Minimum Spanning Tree also has n-minus 1 edges,

this means that our tree equals some Minimum Spanning Tree.

So, our tree is a Minimum Spanning Tree.

This way suffices to prove the statement that at every step,

the current set of edges is a subset of sums of Minimum Spanning Tree.

We'll prove it by induction on the Step Number,

we call it S. The very beginning, when we have no edges,

clear it, empty graph, empty tree,

is a subgraph of a Minimum Spanning Tree.

Induction hypothesis says that we prove the statement

for step K. And now we want to extend it to the next step,

to the step number K plus 1.

We'll show that there exists a Minimum Spanning Tree,

which contains the first K plus 1 edges chosen by Kruskal's Algorithm.

And here's how I did it: assume this is some Minimum Spanning Tree which

contains the first K edges chosen by Kruskal's Algorithm.

You see, there is some edge, we'll call them edges e1, e2 through ek.

You see, it contains edge e1,

e2 or other edges and it contains edge ek minus 1, and edge ek.

Assume it for some reason doesn't contain the next edge, ek plus 1.

Then let's add this edge to this graph.

Now, we have n edges and the graph on n vertices,

it's not a tree anymore,

which means it contains a cycle.

Here is a cycle and let's find an edge in

the cycle which is not chosen by Kruskal's Algorithm yet.

There must be one edge which does not belong to e1 through ek,

because this set of edges chosen by Kruskal's Algorithm never contains a cycle.

This means in this cycles there must be different edge.

Let's say this is this edge f. What can we say about the weight of edge f?

Since Kruskal's Algorithm chose edge ek plus 1 rather than edge ek

and it always chooses an edge of the smallest weight,

it means that the weight of ek plus 1 is less than

or equal to the weight of this edge f. And now,

we can remove the edge f from the graph and add the edge ek plus 1.

Again, we have a connected graph with n-minus 1 edges,

we have a tree and it has at most that weight,

which means it's also a Minimum Spanning Tree.

So we constructed a minimum Spanning Tree

which contains k plus 1 first edges chosen by Kruskal's Algorithm.

We just proved the induction step.

We just proved that there are existing Minimum Spanning Tree

which contains the first k plus

1 edges chosen by Kruskal's Algorithm and now induction finishes the problem.

Minimum Spanning Tree

Introduction to Graph Theory

Meet the Instructors