To answer the question I ask in the previous section we will have to prove Euler's Theorem. Remember we ask the question whether the reason Eulerian cycle ends as graph. And, I will first ask, is the graph for 4-universal strings balanced? And by balanced graph, I mean the in degree of every vertex is equal to the out degree of every vertex. And you can check that this specific graph Is balanced. And of course, every Eulerian graph is balanced. Because if you can find a walk, visiting every edge exactly once, and this walk and per se the ending axis let's say K times, then it has to leave the same vertex the same number of times. So which means that the number of incoming edges in every vertex is equal to the number of outgoing edges from every vertex. So this is very simple. Or what is less trivial is, as Euler's proof, every balanced graph is Eulerian. Which means as soon as we prove that the graph is balanced, there must be an Eulerian cycle in the corresponding graph. To prove Euler's Theorem, we will need to recruit an ant. And let it randomly walk through the graph. Of course, the ant cannot use the same edge twice, because we want the ant to generate an Eulerian cycle in the graph. If ant was a genius, he would simply start from an arbitrary vertex in a graph and start walking along the graph. And chances are that by the end, the ant would generate Eulerian cycle right here. And ant can go home, because we have an Eulerian cycle. But a less intelligent ant would start walking, and may get stuck at some vertex. But in what vertex an ant can start? You have to prove that the only vertex the ant can start is the vertex where the ant started, which means this red vertex. Well, what should we do next? Because we have not visited all edges of the graph yet. So the ant has completed a cycle but it's not a Eulerian. Can we somehow enlarge this green constructed cycle? Well, please note that maybe we should start at a different vertex of this green cycle. Which one? Probably the vertex where there are still some unexplored edges of the graph. So let's try to start in this vertex. And we have chosen this one because there are edges that have not been traversed by the ant. We will have to give the ant different instruction. The ant now doesn't just start walking randomly in the graph because It may end up in the same incomplete cycle. Instead, we first have ask the ant to traverse the same green cycle starting from the new vertex. So it will go here, here, here, here and then return back to the red vertex. However, the ant's work is not over yet because now he can continue. And he continues working, working, working and finally returns back to the same red vertex. So we successfully enlarge our green cycle and it's now green-blue cycle. But what do we do next? We are stuck again but let's repeat the same procedure. Let's find a node where there are still unexplored edges. Here is a vertex with still unexplored edges. And let's once again force our ant to traverse previously constructed green-blue cycle. So let's go, continue, continue, continue, continue, continue. We return back to the red vertex, but now there is a possibility to walk further. We continue enlarging the green-blue cycle. Continue. Continue and finally, the ant proved Euler's Theorem. It constructed the Eulerian Cycle. And this is an example of constructive proof. When the proof of the theorem immediately implies an algorithm for constructing color and cycle. However I have to warn you, this is not the most efficient algorithm for constructing color in cycle. And we will ask you to construct a linear-time algorithm for building an Eulerian Cycle in the graph. And after implementing the linear-time algorithm for constructing Eulerian cycle, you will be able to solve the universal string problem for any reasonable k even let's say for k = 20. The only question left is that in these graphs there are actually many universal strings. And that's fine because any universal string would solve the universal string problem. But in general assembly, there are also often many possible Eulerian cycle but only one of them corresponds to real genome. And in the next segment, we will learn what biologists do to sequence the genomes today. And to address this challenge. [MUSIC]