So we're ready to talk about a slightly different graph problems, and the hopes of maybe finding one that is tractable. In this video, we're going to be defining an Eulerian circuit for a graph. We'll be determining whether graphs are or aren't Eulerian, and we'll be talking about the algorithmic questions surrounding Eulerian graphs. Now, it's worth saying that this lesson is very abstract. And this whole week's material really, does feel a lot more theoretical, than what we've been doing in the courses up until now. We're a little bit more removed from the project. We're a little bit more removed from applications. And there's two reasons for that. One is that, at least I think theory is really really cool. It's what I study, it's what I do research in, it's what I love, and so it's really wonderful to be able to share that with you. But the other reason is also that the theory and the concepts that we're talking about really do end up having some very concrete applications to real problems. And we'll actually be able to have a guest visitor tell us a little bit about that at the end of this module, so stay tuned. Alright but, back to Eulerian graphs and back to these somewhat abstract notions, we talked in the previous video about Hamiltonian graphs and Hamiltonian graphs was a graph where we could walk along all the vertices visiting each vertex exactly once. And so let's tweak that a little bit and we say, okay well in the graphs, we've got vertices, we've got edges. What if we change the definition to ask what an Eulerian graph where we can walk along the whole graph, visiting each edge exactly once. And so in this setting, we're allowed to visit vertices more than once. But what we want to make sure is that each edge gets traversed exactly once. And so let's think about some concrete graphs and think about whether they're Eulerian and so what about this one? Can we traverse this graph visiting each edge exactly once? Okay, so let's see an Eulerian path through this graph, it is in fact Eulerian. We start at the top. We can go around the side, and then come to that middle vertex. Now, we wanna make sure we get that edge between the middle vertex and the top vertex, and so we follow that edge up, and then we go back around the other side. And so this graph is Eulerian, but notice that it's also Hamiltonian. And the Hamiltonian path that we could take through this graph has to be different from the tour that we just did. And so a Hamiltonian path through this graph could just go around the periphery and visit each vertex exactly once. But notice that the Hamiltonian path will not traverse that middle edge. And so it won't be a witness of being Eulerian. All right, what about another graph? Let's take a look over here. Is it Eulerian? And is it Hamiltonian. All right, so in this graph we see that there's an Eulerian tour through the graph. We can start in the middle and follow all the edges in the top triangle, then follow all the edges in one of the side triangles, and then follow all the edges in the third side triangle. And so we get an Eulerian graph. But it's not Hamiltonian, because think about what that description that I gave for the Eulerian tour just did, it had to keep coming back to the middle. And any attempted walk through this graph that tries to visit all the vertices or all the edges will still have to come back to that middle vertex and that's going to be a problem with being Hamiltonian because we're not allowed to visit any vertex more than once. So we've got a graph here that is Eulerian, but not Hamiltonian. One more, is this Eulerian? All right, so you saw that this graph is not Eulerian, and we can do an analysis that if we try to traverse any one edge, then what we do is either we get from a periphery to the middle or the middle to the periphery. If we went from the middle to the periphery then we'd be stuck. We'd be at a periphery vertex with no way of getting back other than going along an edge that we've already traversed. Bad news. If we went from the, from a periphery vertex to the middle vertex, at the beginning then we could have one more hop from the middle to a periphery, but then there's one edge and one vertex that we won't have traversed. And so, there's not going to be any Eulerian to work through this graph, and similarly no Hamiltonian path through this graph, as we saw in the previous video. All right, one last example. It's really useful to see all the different combinations that we can get, and so in this graph we saw before that it is a Hamiltonian graph and is it Eulerian? Okay, so you saw in the quiz, that this is not an Eulerian graph, so we have an example of something that's an Eulerian graph but is Hamiltonian. The point of these four examples is to show that all possible combinations of being Eulerian or not and being Hamiltonian or not are possible. And so even though all we did was tweak just about that one word in the definition, we get very, very different notions when we're talking about Eulerian graphs and we're talking about Hamiltonian graphs.