0:11

[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.

1:52

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.

2:54

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.

3:33

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.

7:36

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.

8:40

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.

9:54

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.