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.