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? And the same for the vertex h, we have two incoming edges. And two outgoing edges. Okay, so this graph is balanced and our goal is to construct an Eulerian cycle in it, okay? What we're going to do is just to go for a walk in this graph. Let's start walking from some node and in this case, let's start walking from a. So, we walk from a to b, and then we walk from b to c. So since our graph is balanced, 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 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. 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? Okay, finally, let me mention, let me conclude this video with mentioning that the method, actually, that we use to prove that there is an Eulerian path to this graph can be easily transformed into a program or into an algorithm. And indeed, for this program for finding Eulerian cycles or path in the graph, they're very efficient algorithms in practice. So even if in your graph there are millions of edges and millions of nodes. It is very easy to find an Eulerian cycle just in the blink of an eye.
