[MUSIC] [SOUND] Hello, everybody, last time I promised you that today, we would talk a lot about walks and closed walks and that's actually what we're going to do. So last time I also showed you a picture of this beautiful national park and today I show you a map. So this is the path map of this park, here is the entrance gate. And when I visit this park, it is so beautiful, I want to visit everything. And nice thing about this park is actually to walk around it. So I want to walk around everywhere where I can, but I also get easily bored. So I don't want to walk every path twice, so now let's see whether I can do that. So for example, if I start at the entrance gate and I take a left here and I go back and I'm here, so where should I go? Well, of course, I mean at some point, I must do this, but then I'm back at the entrance gate and I haven't seen the whole park. So I have to go back and I see things twice. So I made a mistake, that was not a good choice. So let's have another try, let's look closer at the map and see what I should do. What if I start here, and then I don't turn left, but let's say I go straight. I go on to the summit, I enjoy the view, I hike down again, I'm getting hungry, so I go to the Treehouse to have lunch, I continue. Now I'm back where I was, but that's okay because only for a minute and I continue here. I go like this, this, this, and finally in the evening, I go back to the entrance gate and I can go back to my hotel. All right, so in this map, I was able to walk from the entrance gate and in the end, I arrived at the entrance gate and I visited every edge of this graph exactly once. So I did a close walk that visits every edge exactly once. So this is called an Euler cycle, Eulerian cycle or an Eulerian work named after the famous first mathematician Leonhard Euler from 18th century. And it is named by him because he, at this time, he solved a puzzle that was popular in 18th century Europe. So it is a riddle about the city of Koenigsberg, which back then was located in Prussia, and nowadays it's called Kaliningrad and it's located in Russia. Well, actually the city didn't relocate, but the countries changed their borders. Anyway, this is not a history lesson. So as you can see here, there is a map of 18th century Koenigsberg, it has, there is a river, there is an island in the river, and there are several bridges. Actually, there are seven bridges, one, two, three, four, five, six, seven, here. And the riddle is, can you maybe you stay here, here's your hotel, can you get up in the morning, make a tour that visits every bridge and in the evening, it brings you back to the hotel, but you visit every bridge exactly once. So we can actually formulate this as a problem in graph theory. We have a these four vertices, we have these edges. So actually, it's not a graph, but it's a multigraph, but never mind. And then we can actually forget about the rest of Koenigsberg and just focus on this graph. And now the question is, is there a closed walk that visits every vertex? So if there is, then it doesn't actually matter where we start. We could start anywhere, and if you try to quickly figure out, it's not possible. And Euler gave a very simple reason why it's not possible. So look at this vertex here, let's say your hotel is located there, so if you visit this bridge, you go out and at some point, you enter this island again. So you have used two edges, then you go out again and you come back and now you've visited four edges. But now, no matter in which order you do, there will always be one bridge left that we haven't explored yet. Because this vertex has degree five and every time you leave it and you come back, you use two edges and therefore, you'll never be able to visit all the edges. So this does not have an Eulerian walk because it has an odd degree vertex. So here is the definition of an Eulerian cycle as a closed walk that visits every edge exactly once. And there are two obvious obstacles for a graph to have an Eulerian cycle. The first is if G is disconnected, then obviously, you don't have such a cycle because you simply cannot get from one part to the other. And the other is, if G has an odd degree vertex, No matter, let's say you start here, you go out, you come in somehow, you go out, you come in. And in the end, there will be at least one edge left that you cannot take. Okay, so these are two obvious obstacles. So if your graph is disconnected, or it has an odd degree vertex, then your graph does not have an Eulerian cycle. And the cool thing is, that there is a theorem that these are the only two obstacles, which means if a graph is connected and every vertex has an even degree, then it has an Eulerian cycle. So this is called a characterization, you have an if and only statement. You have a condition that's necessary and sufficient. So now let's try to prove this theorem. As often, we start with a definition. A partial, Euler walk that's abbreviated as a PEW, so a PEW is a walk, That visits every edge, At most once. And this definition is good, because it allows us to start with a partial Eulerian walk, maybe the empty walk where we just stay at the vertex. And then gradually enlarge our walk until we have a walk that visits all the edges. So now the strategy is, Grow the PEW until it visit all edges. So there are two cases. Case one, Your walk is not closed. So it could look like this, you start at u and you end at v, and it could look like this. You intersect yourself, you might go to v, you might go back, you might actually go back to u but in the end, you end up in v. From my notes, this walk is in some way a subgraph of your original graph. And in this subgraph, u has odd degree, and v has odd degree, and every other vertex has even degree. So because in your original graph, every vertex has even degree, it means there must be an edge that is incident to v, that you haven't explored yet. So lets call this vw, and then let's just say, you take your PEW and you add the edge vw, and this is also a PEW. So we managed to make it larger. Case two, The PEW is a closed walk. So we started at u and we go around and at some point, we end at u anymore. So don't be fooled, this might actually self-intersect, I just drew it as a circle because it looks more nice, but, Don't be fooled, it could self-intersect. So keep this in mind, so there are again, two cases. First of all, if this already explores every edge, then we are done, right? Otherwise, there is an edge that we haven't explored yet and this edge could, for example, look like this. But then of course because our graph is connected, there is a path from this edge to u. So let's say there is a path from v to u, and at some point, it must hit the circle that we already have, it must hit the closed walk that we already have. And now it's of course obvious what you do, we just call this vertex x and we call it y. And then we can just start at w, we go to v, we go down to x and now we can actually go all the way back to x. And this is basically now a larger PEW. Of course, you have to be a little bit careful because it could be that actually your edge looks like this, but that's not a problem. In this case, you would also just start at w, go to v, and then go around in the circle or it could actually also be that you have an edge that looks like this, w and v. But also there, you can start at W go to V and then just go around the circle once and still you have found a larger partial Eulerian walk. So this means as long as your walk doesn't explore all the edges, you can extend it. Because if you take an edge that you haven't explored yet, there must be a path from your edge to your PEW because your graph is connected. So you do that, and then you go around and you have found a larger PEW. And you iterate this as long as you can do and in the end, you will find a PEW that explores all the edges and this is your Eulerian walk, okay? It's very simple. That's it for today, thanks. [MUSIC]
