We are now in the 18th century Königsberg in Prussia. There are seven bridges, as you can see on the map, and the favorite evening activity of the local people was the plan a walk which would go through every bridge exactly once. But in 1735, the famous Swiss mathematician Leonhard Euler proved that it's impossible. And that was the first result of the graphs theory. This is where graph theory originates from. Let's see why it's impossible. Here's a map of Königsberg. Clearly, we can ignore all the roads and buildings on this map, they're not important for our goals. So, we can simplify this map and just look at this new one, where we've four pieces of earth connected by seven bridges. We can actually forget about the original map. This new one is equivalent to the original one for our goals. We can also give names to these four islands. Let's say this one is called B and these ones are called A, C, and D. Now, as always, I'll draw four circles such that each circle corresponds to an island in the original map. And I connect two them by a line, if and only if there is a bridge between two of them. For example, there is a bridge between B and C, so I can name them in my new drawing. I also draw the remaining six bridges. Those connections are often called edges. So now I want to find a path which goes through each edge exactly once. Such a path is called Eulerian Path. It's named after Euler because he was the first one who discovered all the details here. Let's look close at that Eulerian path. It has some start point and some end point. Let's look at the points in the middle. We enter each point once and leave it once. So we have at least two bridges connected to this point. We can later enter at this point one more time but will leave it as well, and we'll have four bridges and four neighboring points. Now we can enter it one more time and leave again. In this case we have six neighbors which means that in Eulerian Paths, every point, except for the start point and the end point, have an even number of neighbors. Now let's look at our original problem. We have four points and each of them has three neighbors. Three is an odd number, there is no Eulerian path in this drawing because if there was one then every point, except for maybe two, would have an even number of neighbors, which is not the case here. This is exactly how Euler proved that there is no walk crossing each bridges exactly once in Königsberg. Today Königsberg is Kaliningrad in Russia and some of the seven bridges were destroyed during the war and some new ones were recently erected. So now there are six bridges in Kaliningrad. Can I find a walk which causes each bridge exactly once, now? Okay, first let's again draw these four points and connect a pair of them by a line, if there is a bridge between them. So we can work with this picture now. And we see that two points here B and C, have odd numbers of neighbors. Now if there is an Eulerian Paths in this picture, then B and C must be first and the last points in that path. Let's try to find such a path. Let's start with B and go to A, then we'll go to C, to D, then maybe to B, to C, and to D again. I succeeded, we found a path which crossed each bridge exactly once. So now, in Kaliningrad, it is.