Commons license.

Your support will help MIT OpenCourseWare

continue to offer high quality educational resources for free.

To make a donation or view additional materials

from hundreds of MIT courses, visit MIT OpenCourseWare

at ocw.mit.edu.

PROFESSOR: So welcome to this week.

We're going to talk about trees mainly.

We're going to talk about some very special ones,

spanning trees.

But before we do this, you will go

through a whole bunch of definitions

and look at examples to explain how it works.

So let's talk about walks and paths.

So you've already seen a bit of graph theory.

We've talked about graph colorings and so on.

But now we're going to talk about special types of graphs,

and special structures within such graphs.

Well, let's start with the first definition.

How do we define a walk?

Well, a walk is something very simple.

You walk from one vertex in the graph over an edge

to a next vertex, to a next vertex, and so on.

So how do we define this?

A walk is a sequence of vertices that are connected by edges.

So for example, we may have something

that looks like a first vertex.

That we call the start.

And an edge that goes to a second vertex.

We continue like this until the end,

say, at vk, which we call the end of the walk.

And if you look at this, we say this

is a walk from v0 all the way to vk.

It has exactly k edges.

And we say that the length is actually equal to k.

So this is a very basic notion.

And what we are really interested in

is actually paths.

And paths are special types of walks

in which all those vertices are actually

different from one another.

But let's first give an example of a graph

that you will study throughout the whole lecture, especially

when we come to spanning trees.

So let's have a look at the following graph.

So let this be a graph.

And for example, we can have a walk that

goes from this particular edge.

Say we call this v0.

It goes over this edge over here.

Suppose I want to end over here.

Well, I can go many ways in this particular one.

I can go for this edge.

I may go over here.

I may go all the way to this part over here.

I may return if I want to.

And I finally, I take this edge for example back to--

over this edge, I will end in the last vertex vk.

So what we notice here is that we

have a walk that actually gets to this particular vertex,

and then returns to this vertex.

So for a few other edges, and then goes all the way to vk.

So if you talk about the path, then we really

want all the difference vertices not to occur twice.

So let's define this so the destination is

that a path is actually a walk.

Is a walk where all edges, where all vertices,

vi's, are different.

In this particular case-- well for example,

if you strip off this part over here,

you will get a path from v0 to here, to here, to here.

And all these vertices on the path on this walk

are different.

And therefore it is a path.

This also shows us something.

It is possible to construct from a walk a path.

As you can see, we started off with this particular walk.

And we just deleted, essentially,

a part where we sort of came back to the same vertex again.

And when we delete all those kinds of parts,

you will end up with a path.

So can we formalize this a little bit better?

Then we get the next lemma.

I call this lemma one.

And let's see whether we can prove this.

So we want to show that if there exists a walk from, say,

a vertex u to-- well, maybe I should not use arrows.

That's confusing-- from u to v. Then there

also exists a path from u to v.

So how can we prove this?

Do you have any ideas?

So what kind of proof techniques can we use here?

And maybe one of the principles that we have seen?

AUDIENCE: [INAUDIBLE] but I have an idea

about how you could show this.

It's basically if you visit one vertex-- let's

you go 1, 2, 3, 4, 5, 3, 6.

You can walk from 1 to 6.

Then we just take out the 4, you just go 1, 2, 3, 6.

PROFESSOR: Right.

So what did we do there?

We essentially had a walk.

And then we cut out a smaller parts here

that recurs in a sense.

And we have shortened the path, we have shortened the walk

to a smaller path.

So what we've used here is we can sort of take out

parts of the walk just like we did over here

until the walk gets shorter, and shorter, and shorter.

So maybe one of the things that we may consider

is a walk of shortest length.

And we know that this is possible.

Oops, sorry about that.

So let's prove this.

So for example, suppose there exists such a walk from u

to v. Then we know by the ordering principle

that there exists a walk of minimum length.

So that's what we're going to use here.

And then we're going to essentially go

in the same direction as what you were talking about

because we're going to show that it's not possible to delete

anything more.

Because otherwise, if you could do that,

the walk would get shorter.

And that's not possible, because by the well ordering principle,

we simply consider that there exists a walk of minimal length

that we are interested in.

We will show that this particular walk is actually

going to be a path.

So let's see how we can do this.

So let's do walk be equal to-- well, it starts in v0.

It's equal to u.

There's an edge to, say, v1.

It goes all the way up to vk, which is the last vertex, v.

So what are we going to prove?

We're going to prove that this is actually a path.

And since this is a walk of minimal length,

well suppose it is not a path.

So we are going to use contradiction.

Well if it's not a path, then by our definitions over here,

there must be two vertices that are actually

the same, just like in here.

So we go from v0 to, say, this particular vertex, or this one.

And then we come back to this one,

and then all the way to vk.

So if it is not a path, then two of those

must be equal to one another.

And then we are going to use this trick.

We're going to take out this part.

We get the shorter walk.

But that contradicts that our walk is minimal length.

So that's sort of the proof technique that we're doing.

OK.

Let's do this.

So first, let's consider a few cases.

If k equals 0, then that's pretty obvious.

We have only a single vertex u that is connected by a 0 length

path to itself.

So this is fine.

For k equals 1, we have just a single edge.

And then we're done too.

That's a path as well.

So let's consider the case where k is at least two.

Well, suppose it's a walk.

It's not a path.

So we are going to assume the opposite.

If it's not a path, then we concluded

that two of those vi's must be equal to one another.

So there exits an i unequal to j such that vertex vi equals vj.

Ah, but now we have a walk that goes

from v0 all the way to, say, vi, which is equal to vj.

And then we go all the way up to vk which is equal to v.

So essentially, we have created a shorter walk.

We have taken out this little triangle over here.

Now this is a shorter walk.

And this contradicts our assumption of minimality.

So that means that our assumption over here

is not true.

So the walk is actually a path.

So this concludes the proof.

So even though this lemma is pretty

straightforward in the sense that we all

feel that if you have a walk, then you can create a path,

if you really want to write it down with all the principles

that we have been taught, you can see

a few things appearing here.

So we first started with the well ordering principle.

And also we used the method of contradiction in our proof.

So let's set talk about the next definition.

So we talked about walks and paths.

Let's talk about connectivity.

We actually defined two vertices, u and v

to be connected if there is a path that

connects u to v. So u and v are connected

if there is a path from u to v.

And now we can talk about the graphs that are connected.

That's a very important concept.

A graph is connected if every pair of vertices is connected.

So when every pair of vertices in the graph are connected.

So an example is the particular graph on the blackboard.

You can see here that there's always a path

to be found from this vertex, to this one, or to that one,

to this. to that, to this, or that.

You can do this for any two vertices.

So this is a connected graph.

A graph that is not connected looks something

like this for example.

You may have a single edge plus, say,

another triangle, maybe with another edge

or something like that.

So they are disconnected from this vertex.

I do not have a graph that connects

to this vertex over here.

So this is about connectivity.

And now we can start talking about cycles and closed walks.

Together, these concepts will help us to define trees.

And then we can start talking about this very

special concept, spanning trees.

So let's see how that works.

So cycles and closed walks.

We first define a closed walk.

And once we have done this, we are able to get into cycles.

So what's a closed walk?

Well, it's actually a walk for which the start and the end

vertex are the same.

So it starts and ends at exactly the same vertex.

So this is all pretty straightforward.

So we have v0 connected to, say, v1, all the way up to vk.

And vk itself is equal to v0.

So you have a walk that goes all the way

from v0 all the way back to vk.

For example, in this graph, you could have walked all the way

back to v0.

You would have a closed walk.

So what's a cycle?

A cycle is a little bit more special

in which all these vertices over here

are actually different from one another.

So if k is at least three-- so the walk

is not just a simple edge, or just a single vertex.

And if all v0, v1, all the way up to vk minus 1 are different,

then we are saying that we have a cycle.

Then it is called a cycle.

So these two concepts, connectivity and cycles,

will help us to define trees.