[MUSIC] Hello, welcome back to our online course. Remember last time we talked about Eulerian cycles and we proved that a graph has an Eulerian cycle, or I should rather say an Eulerian closed walk. Anyway, a graph has an Eulerian cycle if, and only if, it is connected and every vertex has even degree. And the theorem was not very difficult to prove. Today, we're going to talk about something that's almost the same. It's called a Hamilton cycle. A Hamilton cycle is a cycle in a graph that visits every vertex exactly once. So why should this be so radically different? Well this is a surprising thing, it sounds very similar but it is radically different, it is much more complex. So for example when a none computer science friend of mine asked me what is complexity theory about? What is discrete math about? I tell them these two problems. And then I tell them they sound very similar, but one is super easy and the other is very, very different, it's very, very difficult. And today, we're going to talk about this complex, more difficult problem, Hamiltonian paths and cycles. So you remember, last time I took you to this beautiful park somewhere in nature, some national park. Today, I want to take you to the suburbs of Beijing, the capital of China. So what you see here is a map of the so called New Summer Palace in the north east suburbs of Beijing, if you ever have a chance to go there, don't miss it. It is a beautiful park in a beautiful setting. I kind of made this map by myself, but that's kind of the way it looks. So in this park, you have a couple of lakes and a lot of green space. And of course, a lot of sites. Temples, pagodas, a marbled boat, and everything. So, if you pay the entrance fee, of course you want to visit all the sites. For example, I just named three of the sites that you shouldn't miss. But let's say, I go to the park and enter at the east gate. My goal is to go there and to visit every site. So, the site here are these little orange dots, little orange vertices, and the edges, these are just the paths where I can walk. So my goal is to find a cycle where I start at the east gate and in the evening I come back to the east gate and I visit every vertex exactly once. So, let's try. This is not so easy so maybe I fail, okay let's try it, I start at the east gate then I make my way up here, then I go maybe up here. I think this is called the long corridor or something. And I have to be careful, I have to be careful. Maybe I go up here. I go back a little bit, now I go uphill to the big temple. I go to Suzhou streets, maybe I have lunch there, I go back and I go down hill again, I go back to the lake, I visit the marble boat. And then I pass this bridge and then now I'm on this narrow land bridge between the lakes. And now I'm home free because I can still go back. Here actually once I went there in I think early March or February and I saw a guy winter swimming where there was still ice in the water, it was kind of impressive. Go to the small island and go back to the east gate and then I go home. So here you have a path, you have a cycle that visits every vertex. Now let's try to do the same in the national park that we had visited last time. I start at the entrance gate, maybe I go here. So what should I do now? Now you see, actually, we've run into a problem. So I want to visit this vertex and this vertex, so at some point I must cross over this edge. So there is no choice but to go here. But then I have to continue to here, and if I have to go back to the entrance gate without visiting any vertex twice, I have to go back. So here it's not possible, as you can easily see. So here is the definition of a Hamiltonian cycle. It's just a cycle that contains every vertex. In other case it's a subgraph, Isomorphic to the cycle on end vertices. That's a Hamiltonian cycle or Hamilton cycle. Here are some examples. This is the graph of the dodecahedron. One of the five platonic solids. Take your time and find the Hamilton cycle. I promise you, there is one. And as a spoiler alert, if you can't find it but really want to find it, well Wikipedia is always the answer. Anyway, so here you can find the Hamilton cycle. How about this graph? Let's try it. Let's start at this vertex at the very top and let's go around like this. So this, And now I see, I'm in a problem because I end up at a vertex where I can't go back. So this is not a Hamilton cycle, but here, I have a subgraph. That is isomorphic to the path of length n-1. So, I have a path that visits all the vertices but it doesn't end where I started, so this is called a Hamilton path. So, you can try to find a Hamilton cycle in this graph but as a warning it does not have one. But you can try to figure out why it doesn't, okay. So that's a Hamilton path. So remember last time we proved this beautiful theorem that a graph has an Eulerian cycles if and only if the two following conditions are met. It is connected and every vertex has even degrees. So these conditions are obviously necessary but the cool thing is they're also sufficient. So now what we want we want a theorem that says a graph has a Hamilton cycle if and only if (1) some obviously necessary criterion is met and some other obviously necessary criterion is met. That would be really great if we could prove such a theorem but unfortunately, there probably is no such theorem at least it's not known as we speak and probably it does not exist. So here are some obviously necessary conditions. If G has a Hamilton cycle then well, It is connected. Every vertex has degree at least two. Third, it doesn't look like this. Fourth, it doesn't look like this. By the way, such a thing is called a cut edge, Or a bridge. Right, an edge, if you take it out, it disconnects your graph. And this, here, it's called a cut vertex. You can take it out, and it disconnects your graph. So it doesn't have a bridge, it doesn't have a cut bridge, that's pretty obvious. But how about sufficient conditions? Well, actually, what you should do, you should try to find more necessary conditions. And see how far you get. What about sufficient conditions? Well here is a theorem that is an example of a sufficient condition. It says, if you take two vertices and they are not connected directly by an edge, if for all such vertices, their total degree, if you add up the degrees, if this is at least n, then it has a Hamilton cycle. So for example, you have a vertex here, you have a vertex here that don't have an edge, but together they have many edges. So the sum is at least n. So a degree of u plus degree v Is at least n. So actually that tells you that they actually must have a common neighbor or something. Anyway if this condition is met for every vertex then it has a Hamilton cycle, that's Ore's theorem from 1960, that's what we're going to prove today. So how can you prove this theorem? Well let's simply try. You start with a vertex, you go on, you go on, and because maybe you always find an edge that leads you to a new vertex but it could also be that at some point you get stuck. So it could be, you end up at a vertex u and all the edges, all the neighbors are somewhere on the path. Okay, it could look like this. And well then we're stuck, there is no easy way to extend the path. So now what can we do? Well we can give names to these vertices that's v1 that's vi and let's say vd. So d is the degree of u. Okay, so what can we do? Well there is a case. Suppose this path is not yet a Hamilton path. So there is a vertex here v that is not in our path yet and by assumption there is no edge between u and v. So therefore, the degree of u plus the degree of v, Is at least n. So, this probably tells you that v and u must have a common neighbor but that doesn't really help you. What helps you is the following, you look at the path that we've already found and you look at the successor of every of these vertices and you call it w. So this would be wi and this is wd. And now this inequality tells you that v has large degree. It has degree at least n minus d. So it looks like this, this is v, it has a bunch of neighbors, and it has a bunch of non-neighbors. And this set here has size at most, It has size at most, yeah, at most d, well actually v is a non-neighbor of itself I should kind of draw it differently. Let's see so kind of we have a set here, that's a set of non-neighbors and this has size at most d. And of course it contains u. Right, because by assumption u and v are not neighbors, so it contains u. So besides u, it contains d minus 1, at most d minus 1 vertices. Which means it cannot contain all the w vertices, which means there is a w vertex somewhere in the neighborhood of v. So it means there is an edge from v to wi. Okay, and now this gives you a longer path. Now let's see, where is the longer path? So we start at v, we go here. Then we go to u, we jump to vi and we go all the way back where we started. And now this is a path whose length is one more than the path that we had. So we can always extend our path. Well until we find a Hamilton path then obviously we can not extend it. So you see in the end, we'll find a Hamilton path. Let's say the last vertex is called n and the first vertex is called 1. There are two cases. Case one, 1,n is an edge. Well this is easy, because then you are done, right? Then this is your Hamilton cycle. But suppose there is no edge. Well then there is the same game then we say well the degree of 1 must be at least n minus d. And we do the same arguments but a little bit different, we simply again consider all the neighbors v1, vi until vd of n. And the neighbors to the right w1, wi, wd. And by the same argument n has a bunch of neighbors and it has a bunch of non-neighbors and this set has size at most d, so it contains n so there is not enough space left, well wait wait wait this is 1, this is 1 and it contains n. So there is not enough space left for all the w vertices, so one w vertex has to be outside. And we find an edge from 1 to some wi, and there is your cycle, do you see it? Well, it's a little bit hidden. Yes, so we go from 1 until vi, we jumped to n, we go back to wi, and we can go back to 1, and that's your Hamilton cycle. All right, this finishes the proof of Ore's theorem. It's nice, right? Well, in the literature and textbooks, we usually don't come about Ore's theorem, you come across a corollary of it, which is called Dirac's theorem, it's a little bit older, eight years. And it says, if every vertex has degree at least n/2, then it has a Hamilton cycle. But this is of course a special case, because if every two non-neighboring vertices have total degree at least n, hey, if every vertex has degree at least n/2 then if you pick two vertices, the sum of their degrees is at least n and then you can apply Ore's theorem. But don't be fooled this is a sufficient condition, it's not necessary. So for example, here you see a graph that obviously does not meet the condition of Dirac's theorem or of Ore's theorem but still it has a Hamilton cycle. But still we have a bunch of necessary conditions, we have a bunch of sufficient conditions but we don't have a nice characterization that tells us a graph has a Hamilton cycle if and only if blah blah blah blah blah, right? And this is probably inherent, there is probably no such criterion because there is like a huge theory within theoretical computer science that suggests that actually there is no efficient algorithm to find a Hamilton cycle if there exists one. And if we had such a criterion that tells you well if and only if blah blah blah, this would would in most cases give you an efficient algorithm to find a Hamilton cycle. So therefore most researchers believe this is really a complex problem and you can not find an exact characterization. And with this note, I say goodbye for today. [MUSIC]