We will now make an abrupt turn from universal strings and talk about another classical problem in combinatorics called Bridges of Königsberg. Citizen of Königsberg, and this is 300 years old map of Königsberg, were interested in the following problem. Königsberg consisted of four sectors shown by colored circles here. And these sectors were connected together by seven bridges. So the citizens of Königsberg asked the following question. Can I leave from my home, walk through each bridge exactly once, and return back to my home? And this puzzle is now known as the Bridges of Königsberg problem. And this puzzle, of course, can be transformed into a graph theoretical problem if we connect all four nodes representing four sectors of the city by edges. Every edge corresponds to a single bridge in this city. So if bridge connects sector A with this sector B, then we will connect node A with this node B in the corresponding graph. To solve the bridges of Königsberg problem, what problem do we need to solve in this graph? And of course, you realize that we will need to solve the Eulerian path problem in this graph, or a path visiting every edge in the graph exactly once. And this is a problem that was solved 300 years ago by a great mathematician, Leonhard Euler. If you look at two problems, Eulerian cycle problem and Hamiltonian cycle problem. And we will be, instead of talking about paths, we would prefer to talk about cycles, simply because bacterial genome are usually cyclic genome, circular genome, and we are interested in interesting bacterial genome. Can you find a difference between these two problems? The only difference is that the Eulerian cycle problem talks about visiting every edge, where Hamiltonian cycle problem talks about visiting every vertex. So why did we introduce the Eulerian cycle problem instead of Hamiltonian cycle problem if they are so similar? It will be become clear in a second. Let's return back to the universal string problem, but let's now talk about universal circular string problem, because once again, we are interested in circular bacterial genome. And this problem is to find a circular string containing each binary k-mer exactly once. For example, for 3-mers, for these 3-mers, this is a universal circular string containing them. For example, 101 is encoded here on this circle. We already saw how to solve the universal string problem using the overlap graph. But de Bruijn was not satisfied with this approach. And his idea was to construct the de Bruijn graph of the same string. And that is how the de Bruijn graph of this eight-string looks like. And if we want to construct a universal circular string, we simply need to take an Eulerian cycle in this graph that we are building right now by visiting all edges of this graph. We succeeded building the de Bruijn graph for all 3-mer. And this is a more complex de Bruijn graph for four-universal strings. Does it have an Eulerian cycle? How would we answer this question, particularly if we are interested in a de Bruijn graph for 20-universal strings with over a million vertices? [MUSIC]