Subtitles section Play video Print subtitles The following content is provided under a Creative 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.