[MUSIC] And so now we can ask the same question we asked before, is there an algorithm that determines, given a graph, whether it's Eulerian or not? And that brute force approach that we talked about before would still work, right. We could still generate all sequences of vertices, check whether they're paths and check whether they're Eulerian. And that's fine, but we talked about how it wasn't efficient. And in fact for Eulerian graphs, there's an easier way. And so, if we think back to our two examples of Eulerian graphs from those just toy, basic examples, we can think about how we may have come up with the Eulerian paths that visit every edge exactly once in these graphs. And notice that when we were thinking about these Eulerian paths, It was important which vertex we started with. So for example, in the one graph, we can't start at one of the side vertices. We have to start in one of the two middle vertices, because if we try to start on one of the sides, then we're gonna get stuck and not be able to come to visit every edge. And the algorithm is based on the observation That when we have an Eulerian path we have to have each edge traverse exactly once and so we can think about these edges as taking us to and from vertices. And so what we're doing is we're partitioning all of the edges in the graph and based on the sequence of edges that we traverse in the path and some of these edges bring us into vertices and some of these edges take us out of vertices. And so if we're focused on any one vertex, in order to have an Eulerian path we have to have the same number of edges going into that vertex as are going out of that vertex. And so what that means is that most of the vertices in the graph need to be of even degree in order for there to be an Eulerian path through this graph. And We might be able to accommodate two exceptions. Our starting vertex is allowed to have more outgoing edges than incoming edges, and our ending vertex is allowed to have more incoming edges than outgoing edges. And so the criterion for being is that there's, at most, two vertices of odd degree in the graph. And it turns out that If we have at most 2 vertices of odd degree, then we can come up with algorithmically an Eulerian path through this graph. Just starting at one of those odd degree vertices and figuring out how to go from there. And ditto If we know that our graph is Eulerian we can guarantee that it has at most two vertices of odd degree, and so it's a really cool theoretical theorem that you can prove about this equivalence between this notion of Eulerian and the degree structure of the graph, and, well who cares? One reason is that it gives us a much faster algorithm for determining whether a graph is Eulerian but again who cares. And the reason we care is that, A, we see the small changes in the definition lead to really big algorithmic differences, and, B, what that does is it gives us a direction to go. If we're trying to use graphs to solve real world problems, then what we want to do is model our real world problems in ways that lead themselves to solutions via looking for Eulerian paths or looking for other graph properties that are efficient to determine or have efficient algorithms for them. What we notice is that, when we're looking at the theory of the graphs, that's great. But we want to keep in mind, when those theoretical choices lead to efficient implementations, and those efficient implementations can help us in practice, as you'll see next.