And we are now ready to prove Euler's theorem, that will help us to find paths visiting every edge in the graph exactly once. Actually, we will be focusing on the Eulerian Cycle problem. Find a cycle that visits every edge in the graph, because Euler was interested in a walk in Kernigsberg that starts and ends at the same place. There is cosmetic, very small differences, between finding Eulerian cycles and Eulerian paths. As soon as we learn how to find cycles, we will learn how to find paths, and vice versa. Let us start from a question. Does this graph have an Eulerian cycle? Or, in other words, is this graph Eulerian? Of course not, because there is no way out of the red node. What about this graph? It's also non Eulerian because there's no way in, into the the red node. And what about this graph? We need to look a little bit more closer but we will, immediately find a red node here for which there is one incoming and two outgoing edges. Which means that this graph cannot possibly be Eulerian, because in every Eulerian cycle, the number of times we enter into a node equals to the number of times we leave the node. And therefore, the number of incoming edges in every node should be equal to the number of outgoing edges from every node. We call a graph balanced if, in-degree of every node, equal to its out-degree. Or in other words, the number of incoming edges to every node equals the number of outgoing edges. Is this graph balanced? Of course, we can see that for every node there are two incoming and two outgoing edges. But, it doesn't help us yet to figure out whether there is an Eulerian cycle in this graph. And now, we are ready to present Euler's theorem. We already saw that every Eulerian graph is balanced. So this graph has a chance to be Eulerian. Euler proved that every balanced graph is Eulerian, of course balanced and strongly connected because if graph is disconnected there's no way to find. Let's prove this theorem. And to prove the theorem, we need to recruit an ant, and let it randomly walk through the graph, of course with the condition that the ant cannot visit the same edge twice. Let's start. If ant was a genius, then he would simply walk along the graph. As I show here, visited all edges of the graph, and finally, returned back. But an average ant, wouldn't be that lucky, and it would start travelling through the graph, start walking, and eventually, it would get stuck. Let's stop for a second and think. But to what node this ant can possibly get stuck? Can it get stuck in the middle of the graph? Presumably not, because our graph is balanced, and therefore every time the ant is entering into a node, there should be a way out of the node. This condition holds for all nodes in the graph, except for one. Which one? Of course, it's the starting node of the ant, because in the starting node, the ant has already used the first outgoing edge, so it may arrive in this node and there will be no out going edge left. And therefore what we learn that the ant can only get stuck at the node where it starts. What can we do? Afterwards the ant failed to construct the Eulerian Cycle, because it did not visit. all edges of the graph. But maybe, just maybe, we can start at a different node in the green cycle. Let's start at a different node in the green cycle. Also it's not clear what differences does it make but why shouldn't we try to start in a node in the cycle where there is still unexplored edges. For example, at this node in the cycle, there are still unexplored edges left, so let's force that to start here, at this node, and in the beginning, let's tell them, first follow the same cycle that you constructed in the previous step. So the ant starts walwking along the green cycle. The ant absolutely doesn't understand why he has to do this kind of thing along the cycle that he already constructed but finally he arrives to the initial node and now he realizes that actually now he can continue walking. Because the rest still unexplored edges from this ? node. Then continues walking, continues walking, continues walking, and finally got stuck. And of course it got stuck in the same node where it started. What you should do today, afterwards? Then afterwards, we should start at another node with the still unexplored edges. Where is this node? Can be, well, this is the node, with still unexplored edges. The ant first will be ordered to traverse the cycle that has been already constructed, there's this green blue cycle, and then starts, continue, continue, continue, the ant is not happy but it's okay. Continue and finally, it arrives to the initial node, but now the ant realizes that the instructions are not stupid because there is a possibility to explore it further, and we continue, continue, continue, and finally, the ant constructed the cycle that we wanted, that visits every edge of the graph exactly once. Not only ant constructed the cycle, we actually just came up with this algorithm for doing this and this should accord describe our instructions to the ant, and you can implement it and get real result in an efficient algorithm. And if we would now put an ant to search de Bruijn graphs constructed for universal string, in this case just in three iterations, it will construct Eulerian cycle, and therefore construct a universal string. You can check that you will, can, be able to derive universal string from the cycle.