0:00

So the Eulerian theorem states that a connected graph,

a connected, undirected graph has an Eulerian cycle, if and

only if all the degrees of all its nodes are even, okay?

For the directed case, the theorem states that a strongly connected

graph has an Eulerian cycle, if and only if all its nodes are balanced.

And by saying balanced, we mean that the in-degree of each

node is equal to its out-degree, okay?

So some part of this theorem, of these two criterias, are actually easy to see.

So if we have, for example, let's focus on the directed case.

If we have a cycle that visits all the edges of the graph and

then enters the same vertex and the same node, this actually means that for

each node, the number of times we enter this vertex

was the same as the number of ways we lapped this vertex, right?

Which means that its in-degree must be equal to its out-degree.

So once again, if there is an Eulerian cycle,

then every node in this graph should be balanced.

The difficult part, the not-so-obvious, let me say so part, is the opposite part.

So what we need to show is that if all the degrees are balanced,

then there is an Eulerian cycle.

And this is exactly what we are going to do now.

So we will focus on the directed case.

So as we've just discussed,

if some node is imbalanced then definitely there is no way an Eulerian cycle.

So what we're going to show now is that if each node is balanced,

then there is an Eulerian cycle.

And this is exactly the graph shown here on the slide.

You can check that for every node here its in-degree is equal to its out-degree.

For example, for a we have exactly one incoming edge and

exactly one outgoing edge.

For the node d, for example, we have two incoming edges.

Let me show them.

So these are two incoming edges and two outgoing edges, okay?

2:53

when we enter some node, we always have a place ability to leave this node.

This is just because the number of incoming edges to any node is

equal to the number of outgoing edges.

So what will happen during this walk is that at some point,

we will get out of edges, right?

So at this point, we return back to a and there are no untraversed edges.

Yes, let me also mention that of course,

we are only going to traverse edges that haven't been traversed previously.

Okay, so at this point it seems that we are stuck.

We returned to the node a,

there are no untraversed edges connected to a on one hand.

And on the other hand unfortunately, we haven't yet constructed an Eulerian cycle,

so we are just stuck at a vertex a.

At the same time note that at this point, we just have a cycle.

And also we do remember that our graph is strongly connected.

This means that there should be at least one node

on our cycle which is connected to the rest of the graph.

More precisely, there must be a node in our cycle for

which there are outgoing untraversed edges.

So in our case, one of such nodes is actually the node c.

And also note at the same time that now we have a cycle.

And for the cycles, there is no beginning and no end, right?

So we can start traversing this cycle from any of its nodes.

For example, let's assume that

4:38

we've started to traverse this cycle from the node c, okay?

And it's convenient because we can, on one hand, for

C, there is still some outgoing untraversed edges.

At the same time, we're going from c,

we can easily traverse the cycles that were constructed previously.

We started from c, and we end at c, and then we continued to traverse this, right?

This way, by shifting the starting point of our cycle,

we actually make sure to glue same two cycles.

So I will tell about this more in a minute.

So let's continue traversing our graph from the node c.

So we go from c to d.

We go from d to g and from g to c.

And now we are again stuck at the vertex c.

Okay, let's now see what happened.

On our first iteration, we started from node a and we constructed some cycle.

Okay, this was, very roughly, this is how our cycle looked like.

Then we realized.

So this was vertex a.

Then we realized that in our cycle somewhere there is a vertex c for

which there were some untraversed edges.

And we found some other cycle, okay?

But then through this node c we can glue these two cycles, right?

Because now, we can traverse these two cycles starting from the vertex c.

So we start from here, we traverse the first cycle this way, and

then we traverse this cycle this way.

So this way, we actually get a larger cycle, okay?

We first constructed some cycle, and

then we actually extended by including some additional cycle.

And what we get now is still some cycle that visit some edges.

And there is still not an Eulerian because there are still untraversed edges.

But now, we're going to repeat the same procedure.

Now we have a larger cycle and in this cycle,

there is a vertex g, which still has untraversed edges.

So we might assume that our brown cycle here,

we started to traverse it from g and we traverse all the brown edges.

And then we continue exploring the graph.

So we go from g to h.

And then we get back to g from h.

Now we extended our cycle even further.

And then we continued from the vertex d, which lies in our brown cycle on one hand.

On the other hand, it still has some outgoing untraversed edges.

And this way, we extend our cycle finally to an Eulerian cycle, okay?

And this basically proves our theorem for, for the directive case, okay?

Now the remaining question is, what happens with path instead of cycles?

It is actually not so difficult to reduce this criteria to the criteria

of the existence of Eulerian cycles.

First of all, if we are looking for a path in our graph, then of course,

not every vertex, not every node in every graph should be balanced because for

the path, we have one outgoing edge.

Probably we visit this node once more again.

This basically means that for the starting vertex of our path,

it has outgoing out-degree which is one more than its incoming degree.

And the same is for the end of this path, right?

Then if you would like to get the criteria,

first of all in your graph if there is an Eulerian path,

then these two vertices should be uniquely definable and identifiable.

8:41

There should be a vertex whose out-degree is one times larger than

its out-degree and vice versa for its end vertex, it should be a uniquely

defined vertex whose in-degree is one larger than its out-degree.

But if you add a match from this ending point to its starting point and

then you will get a cycle.

And basically then you can use a criteria form for cycles.

Let me illustrate this on this simple example.

So, imagine the following graph.

So, in this case the in-degrees and out-degrees are as shown on this slide.

So for example, for this vertex, its in-degree is equal to 2 and

out-degree is also equal to 2.

This vertex is also balanced, and this vertex is balanced.

On the other hand, for this vertex we have in-degree equal to 1 and

out-degree equal to 2, which means that this Is the only

vertex that can be a starting vertex of another impasse.

On the other hand, for this vertex its in-degree is equal to 2, but

its out-degree is equal to 1, which means that it is exactly the vertex

that should be the last vertex of an Eulerian path, okay?

Now, let me try to construct the corresponding Eulerian cycle here.

We might, for example, go first here,

then here, then here, then here,

then here, here, here, okay?

So indeed, there is an Eulerian path in this graph.

And particularly, we would like just to find the simple criteriaism.

It remains to note that if we add the following edge from the uniquely

determined end of the path to the uniquely determined beginning of the path,

then what we get is actually an Eulerian cycle in the resulting graph.

And for an Eulerian cycle, we all ready have a criteria.

So a criteria for a path in a directed graph is the following.

So there should be a uniquely determined beginning of the path.

There should be a uniquely determined end of the path.

Such that if you add a match between them,

then the graph should become balanced, okay?